Submission #448572

#	Time	Username	Problem	Language	Result	Execution time	Memory
448572		Deepesson	Traffic (IOI10_traffic)	C++17	25 / 100	114 ms	34040 KiB

traffic

#include <bits/stdc++.h>
#define MAX 210000
typedef std::pair<int,int> pii;
std::vector<int> con[MAX];
int res = 2e9+10;
int ind;
int* pop;
int dfs(int pos,int prev,int dist){
    int max = dist;
    int soma = pop[pos];
    for(auto&x:con[pos]){
        if(x!=prev){
            int r = dfs(x,pos,dist+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: 0 / 25
• Subtask 3: 0 / 25
• Subtask 4: 0 / 25