Submission #229321

#	Time	Username	Problem	Language	Result	Execution time	Memory
229321		thtsshz_bgwrswh	Traffic (IOI10_traffic)	C++17	100 / 100	1353 ms	141292 KiB

traffic

#pragma GCC optimize("Ofast")
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> g[1000005];
long long num[1000005],minv=1000000000000000000;
int n,ans;
long long DFS(int v,int p){
	for(auto x:g[v])
		if(x!=p)
			num[v]+=DFS(x,v);
	return num[v];
}
void DP(int v,int p){
	for(auto x:g[v]){
		if(x==p)
			continue;
		long long pre=num[v];
		num[v]-=num[x];
		num[x]=pre;
		DP(x,v);
		num[x]-=num[v];
		num[v]=pre;	
	}
	long long maxv=0;
	for(auto x:g[v])
		maxv=max(maxv,num[x]);
	if(maxv<minv){
		minv=maxv;
		ans=v;
	}
}
int LocateCentre(int N,int *P,int *S,int *D){
	int i;
	n=N;
	for(i=0;i<n;i++)
		num[i]=P[i];
	for(i=0;i<n-1;i++){
		g[S[i]].emplace_back(D[i]);
		g[D[i]].emplace_back(S[i]);
	}
	DFS(0,-1);
	DP(0,-1); 
	return ans;
}

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