Submission #448574

#	Time	Username	Problem	Language	Result	Execution time	Memory
448574		Deepesson	Traffic (IOI10_traffic)	C++17	50 / 100	499 ms	167864 KiB

traffic

#include <bits/stdc++.h>
#define MAX 1210000
typedef std::pair<long long,long long> pii;
std::vector<long long> con[MAX];
long long res = 2e9+10;
long long ind;
int* pop;
long long dfs(long long pos,long long prev,long long dist){
    long long max = dist;
    long long soma = pop[pos];
    for(auto&x:con[pos]){
        if(x!=prev){
            long long r = dfs(x,pos,dist+(long long)pop[pos]);
            max=std::max(max,r);
            soma+=r;
        }
    }
    if(max<res){
        res=std::min(res,max);
        ind=pos;
    }
    return soma;
}
int LocateCentre(int N, int pp[], int S[], int D[]) {
   pop=pp;
   for(auto&x:con)x.clear();
   res=2e9+10;
   for(int i=0;i!=N-1;++i){
        con[S[i]].push_back(D[i]);
        con[D[i]].push_back(S[i]);
   }
   int start = 0;
   for(int i=0;i!=N;++i)if(con[i].size()==1)start=i;
   dfs(start,-1,0);
   return ind;
}

• Subtask 1: 25 / 25
• Subtask 2: 25 / 25
• Subtask 3: 0 / 25
• Subtask 4: 0 / 25