Submission #722328

#	Time	Username	Problem	Language	Result	Execution time	Memory
722328		Yell0	Traffic (IOI10_traffic)	C++17	0 / 100	1 ms	304 KiB

traffic

#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;
}

• Subtask 1: 0 / 25
• Subtask 2: 0 / 25
• Subtask 3: 0 / 25
• Subtask 4: 0 / 25