Submission #463514

#	Time	Username	Problem	Language	Result	Execution time	Memory
463514		osmanallazov	Traffic (IOI10_traffic)	C++14	100 / 100	1541 ms	152980 KiB

traffic

#include "traffic.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int > pii;
vector<int> adj[1000000];
ll sum[1000000];
pair<ll, int> ans = {LLONG_MAX,-1};
ll solve(int x, int p, int pp[], ll t){
	ll maxx=0;
	sum[x]=pp[x];
	for(auto c : adj[x]) if(c!=p){
		ll sum1=solve(c,x,pp,t);
		maxx=max(maxx,sum1);
		sum[x]+=sum1;
	}
	maxx=max(maxx,t-sum[x]);
	ans=min(ans,{maxx,x});
	return sum[x];
}

int LocateCentre(int N, int pp[], int S[], int D[]) {
	ll total=0;
	for(int i=0;i<N;i++){
		adj[S[i]].push_back(D[i]);
		adj[D[i]].push_back(S[i]);
		total+=pp[i];
	}
	solve(0,-1,pp,total);
	return ans.second;
}

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