제출 #722328

#제출 시각아이디문제언어결과실행 시간메모리
722328Yell0Traffic (IOI10_traffic)C++17
0 / 100
1 ms304 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; void dfs1(vector<vector<int>>& gr,vector<ll>& w,vector<ll>& st,vector<int>& pa,int u,int p) { st[u]=w[u]; pa[u]=p; for(int v:gr[u]) { if(v==p) continue; dfs1(gr,w,st,pa,v,u); st[u]+=w[v]; } } void dfs2(vector<vector<int>>& gr,vector<ll>& st,vector<ll>& pw,int u,int p) { for(int v:gr[u]) { if(v==p) continue; pw[v]=pw[u]+st[u]-st[v]; dfs2(gr,st,pw,v,u); } } int LocateCentre(int N,int P[],int S[],int D[]) { vector<vector<int>> gr(N); for(int i=0;i<N-1;++i) { gr[S[i]].push_back(D[i]); gr[D[i]].push_back(S[i]); } vector<ll> w(P,P+N),st(N),pw(N),mw(N); vector<int> pa(N); dfs1(gr,w,st,pa,0,0); pw[0]=0; dfs2(gr,st,pw,0,0); ll cmw=LLONG_MAX; int ans=0; for(int u=0;u<N;++u) { ll mw=pw[u]; for(int v:gr[u]) if(v!=pa[u]) mw=max(mw,st[v]); if(mw<cmw) { ans=u; cmw=mw; } } 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...