Submission #1018885

#	Time	Username	Problem	Language	Result	Execution time	Memory
1018885		socpite	Traffic (IOI10_traffic)	C++14	100 / 100	647 ms	178512 KiB

traffic

#include "traffic.h"
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e6+5;
const long long INF = 1e18;

vector<int> g[maxn];
long long sz[maxn], mx[maxn];

int dfs(int x, int p, long long tot){
   int re = -1;
   mx[x] = 0;

   for(auto v: g[x]){
      if(v == p)continue;
      int tmp = dfs(v, x, tot);
      sz[x] += sz[v];
      mx[x] = max(mx[x], sz[v]);

      if(re == -1 || mx[tmp] < mx[re])re = tmp;      
   }
   mx[x] = max(mx[x], tot - sz[x]);
   if(re == -1 || mx[x] < mx[re])re = x;
   return re;
}

int LocateCentre(int N, int pp[], int S[], int D[]) {
   long long sum = 0;
   for(int i = 0; i < N; i++){
      g[i].clear();
      sz[i] = pp[i];
      sum += pp[i];
   }
   for(int i = 0; i < N-1; i++){
      g[S[i]].push_back(D[i]);
      g[D[i]].push_back(S[i]);
   }
   return dfs(0, -1, sum);
}

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