제출 #229320

#제출 시각아이디문제언어결과실행 시간메모리
229320thtsshz_bgwrswhTraffic (IOI10_traffic)C++17
0 / 100
19 ms23808 KiB
#pragma GCC optimize("Ofast") #include<stdio.h> #include<vector> #include<algorithm> using namespace std; vector<int> g[1000005]; long long num[1000005],minv=1000000000000000000; int n,ans; long long DFS(int v,int p){ for(auto x:g[v]) if(x!=p) num[v]+=DFS(x,v); return num[v]; } void DP(int v,int p){ for(auto x:g[v]){ if(x==p) continue; long long pre=num[v]; num[v]-=num[x]; num[x]+=pre; DP(x,v); num[x]-=pre; num[v]+=num[x]; } long long maxv=0; for(auto x:g[v]) if(x!=p) maxv=max(maxv,num[x]); if(maxv<minv){ minv=maxv; ans=v; } } int LocateCentre(int N,int *P,int *S,int *D){ int i; n=N; for(i=0;i<n;i++) num[i]=P[i]; for(i=0;i<n-1;i++){ g[S[i]].emplace_back(D[i]); g[D[i]].emplace_back(S[i]); } DFS(0,-1); DP(0,-1); return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...