Submission #241751

#	Time	Username	Problem	Language	Result	Execution time	Memory
241751		davi_bart	Traffic (IOI10_traffic)	C++14	100 / 100	1464 ms	138080 KiB

traffic

#include <bits/stdc++.h>
using namespace std;
vector<int> v[1000009];
int k[1000009];
int mi=2e9,best=0;
vector<int>p;
int dfs(int pos,int prec){
  int val=p[pos];
  for(int s:v[pos])if(s!=prec)val+=dfs(s,pos);
  return k[pos]=val;
}
void root(int pos,int prec){
  int ma=0;
  for(int s:v[pos])ma=max(ma,k[s]);
  if(ma<mi){
    mi=ma;
    best=pos;
  }
  for(int s:v[pos]){
    if(s==prec)continue;
    k[pos]-=k[s];
    k[s]+=k[pos];
    root(s,pos);
    k[s]-=k[pos];
    k[pos]+=k[s];
  }
}
int LocateCentre(int N,int P[],int S[],int D[]){
  for(int i=0;i<N-1;i++){
    v[S[i]].push_back(D[i]);
    v[D[i]].push_back(S[i]);
  }
  for(int i=0;i<N;i++)p.push_back(P[i]);
  dfs(0,-1);
  root(0,-1);
  return best;
}

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