Submission #295173

#	Time	Username	Problem	Language	Result	Execution time	Memory
295173		amiratou	Traffic (IOI10_traffic)	C++14	100 / 100	1617 ms	135672 KiB

traffic

#include "traffic.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
const int MX = (int)(1e6+3);
const int INF = (int)(2e9+1);
typedef pair<int,int> ii;

vector<ii> vec[MX];
int val[MX];

int solve(int node,int p){
	int sum=val[node];
	for(auto &it:vec[node]){
		if(it.fi==p)continue;
		if(it.se==-1)
			it.se=solve(it.fi,node);
		sum+=it.se;
	}
	return sum;
}

int LocateCentre(int N, int pp[], int S[], int D[]) {
	for (int i = 0; i < N-1; ++i)
	{
		val[i]=pp[i];
		vec[S[i]].push_back({D[i],-1});
		vec[D[i]].push_back({S[i],-1});
	}
	val[N-1]=pp[N-1];
	int ans=INF,idx=-1;
	for (int i = 0; i < N; ++i)
	{
		int maxi=0;
		for(auto &it:vec[i]){
			if(it.se==-1)
				it.se=solve(it.fi,i);
			maxi=max(maxi,it.se);
		}
		if(maxi<ans)ans=maxi,idx=i;
	}
	assert(idx!=-1);
	return idx;
}

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