Участник:AlinaS/ADASALES

Материал из DISCOPAL
Перейти к: навигация, поиск

Задача https://www.spoj.com/problems/ADASALES/

Компилятор C++ (gcc 8.3)

Аналогичный код на питоне не проходит по времени.

#include<bits/stdc++.h>
using namespace std;
 
const int maxn=(int)1e5+1;
long long prices[maxn], best[maxn], f[maxn], g[maxn], h[maxn];
long long zero = 0, co = 0;
vector<int> roads[maxn];
 
void DFS(int u, int vs[maxn])
{
    vs[u]=1;
 
    long long res=0, f_max=0, s_max=0;
    vector<int> vt; 
 
    for (int v:roads[u])
    {
        if(vs[v] == 0)
        {
            vt.push_back(v);
 
            DFS(v, vs);
            co = max(zero, prices[v] - prices[u]) + f[v];
            res = max(res, co);
            if (f_max <= co)
            {
                s_max = f_max;
                f_max = co;
            }
 
            else s_max = max(s_max, co);
        }
    }
 
    f[u]=res;
 
    for (int i=0; i<vt.size(); i++)
    {
        int v = vt[i];
 
        co = max(zero, prices[v] - prices[u]) + f[v];
        if (co == f_max)
    	{
    		g[v] = s_max;
    	}
        else 
    	{
    		g[v] = f_max;
    	}
    }
}
 
void DFS1(int u, int vs[maxn])
{
    vs[u] = 1;
 
    for(int v:roads[u])
    {
        if (vs[v] == 0)
        {
            h[v] = max(zero, prices[u] - prices[v]) + max(h[u], g[v]);
            best[v] = max(h[v], f[v]);
            DFS1(v, vs);
        }
    }
}
 
int main()
{
	int N, Q, start;
	int i, ui, vi;
	int tmp[maxn] = {0}, tmp1[maxn] = {0};
 
    cin>>N>>Q;
    for(i=0; i<N; i++) 
    {
    	cin>>prices[i];
    }
    for(i=0; i<N-1; i++)
    {
        cin>>ui>>vi;
        roads[ui].push_back(vi);
        roads[vi].push_back(ui);
    }
 
    DFS(0, tmp);
    DFS1(0, tmp1);
	best[0]=f[0];
 
    for(i=0; i<Q; i++)
    {
        cin>>start;
        cout<<best[start]<<'\n';
    }
}


StasFomin 00:29, 17 декабря 2020 (MSK): А приложите и ваш питоновый код. Может он с PYPY-компилятором уложиться.