Submission #805291

#	Time	Username	Problem	Language	Result	Execution time	Memory
805291		QwertyPi	Traffic (IOI10_traffic)	C++14	100 / 100	750 ms	170760 KiB

traffic

#include "traffic.h"
 
#include <bits/stdc++.h>
using namespace std;
 
const int N = 1e6 + 11;
int p[N], sz[N];
vector<int> G[N];
 
void dfs(int v, int par = -1){
	for(auto i : G[v]){
		if(i != par){
			dfs(i, v);
			sz[v] += sz[i];
		}
	}
	sz[v] += p[v];
}
 
int centroid(int v, int par = -1){
	for(auto i : G[v]){
		if(i != par && sz[i] >= (sz[0] + 1) / 2){
			return centroid(i, v);
		}
	}
	return v;
}
 
int LocateCentre(int N, int pp[], int S[], int D[]) {
   for(int i = 0; i < N - 1; i++){
      G[S[i]].push_back(D[i]);
      G[D[i]].push_back(S[i]);
   }
   for(int i = 0; i < N; i++) p[i] = pp[i];
   dfs(0); return centroid(0);
}

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