Submission #241750

#	Time	Username	Problem	Language	Result	Execution time	Memory
241750		davi_bart	Traffic (IOI10_traffic)	C++14	100 / 100	1494 ms	125280 KiB

traffic

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
//#include "grader.h"
using namespace std;
#define ll long long
//#define int ll
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
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;
}/*
signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int N;
    cin>>N;
    int P[N],S[N-1],D[N-1];
    for(int i=0;i<N;i++)cin>>P[i];
    for(int i=0;i<N-1;i++)cin>>S[i]>>D[i];
    cout<<LocateCentre(N,P,S,D);
}*/

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