Submission #1288780

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288780		WH8	Traffic (IOI10_traffic)	C++17	100 / 100	578 ms	110392 KiB

traffic

#include "traffic.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int LocateCentre(int N, int pp[], int S[], int D[]) {
	ll sm=0;
	for(int i=0;i<N;i++)sm+=pp[i];
	pair<ll,int> ans={1e15, 0};
	vector<vector<int>> al(N);
	for(int i=0;i<N-1;i++){
		al[S[i]].push_back(D[i]);
		al[D[i]].push_back(S[i]);
	}
	auto dfs=[&](auto && dfs, int x, int p)->ll{
		ll mx=0, sub=pp[x];
		for(auto it:al[x]){
			if(it==p)continue;
			ll ret=dfs(dfs, it, x);
			mx=max(mx, ret);
			sub+=ret;
		}
		mx=max(mx, sm-sub);
		//~ printf("at %d, sub %lld\n", x, sub);
		ans=min(ans, {mx, x});
		return sub;
	};
	dfs(dfs, 0, -1);
	return ans.second;
}

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