제출 #502547

#제출 시각아이디문제언어결과실행 시간메모리
502547Fake4FunTraffic (IOI10_traffic)C++14
0 / 100
11 ms23756 KiB
// source: https://oj.uz/problem/view/IOI10_traffic #include "traffic.h" #include<iostream> #include<vector> using namespace std; const int N=1e6+5; int n,p[N]; int t1[N],t2[N],dad[N]; vector<int> adj[N]; void DFS(int pre,int u){ t1[u]=p[u]; dad[u]=pre; for(auto i:adj[u]){ if(i==pre) continue; DFS(u,i); t1[u]+=t1[i]; } } int LocateCentre(int Xn,int Xp[],int U[],int V[]){ n=Xn; for(int i=0;i<n-1;i++){ adj[U[i]].push_back(V[i]); adj[V[i]].push_back(U[i]); } for(int i=0;i<n;i++) p[i+1]=Xp[i]; DFS(0,1); int all=t1[1]; int mi, pos=-1; for(int u=1;u<=n;u++){ int val=all-t1[u]; for(auto i:adj[u]){ if(i==dad[u]) continue; val=max(val,t1[i]); } if(pos==-1||mi>val) pos=u, mi=val; } return pos; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...