Submission #405125

#	Time	Username	Problem	Language	Result	Execution time	Memory
405125		Antekb	Traffic (IOI10_traffic)	C++14	100 / 100	1128 ms	150928 KiB

traffic

#include "traffic.h"
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
vector<int> E[N];
int siz[N];
int opt=2e9, sum, gdzie;
void dfs(int v, int p){
	int res=0;
	for(int u:E[v]){
		if(u!=p){
			dfs(u, v);
			siz[v]+=siz[u];
			res=max(res, siz[u]);
		}
	}
	res=max(res, sum-siz[v]);
	opt=min(opt, res);
	if(res==opt)gdzie=v;
}
int LocateCentre(int N, int pp[], int S[], int D[]) {
	for(int i=0; i<N; i++){
		siz[i]=pp[i];
		sum+=siz[i];
	}
	for(int i=0; i<N-1; i++){
		E[S[i]].push_back(D[i]);
		E[D[i]].push_back(S[i]);
	}
	dfs(0, -1);
   	return gdzie;
}

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