# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
722327 | Yell0 | Traffic (IOI10_traffic) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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,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;
}