Submission #364623

#	Time	Username	Problem	Language	Result	Execution time	Memory
364623		BlancaHM	Traffic (IOI10_traffic)	C++14	100 / 100	1205 ms	170988 KiB

traffic

#include <iostream>
#include <vector>
using namespace std;
typedef long long int ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
 
vl DP;
vvi G;
 
ll dfs(int S, int par) {
	ll ans = DP[S];
	for (int i = 0; i < (int) G[S].size(); i++) {
		int v = G[S][i];
		if (v == par) continue;
		ans += dfs(v, S);
	}
	return DP[S] = ans;
}
 
int LocateCentre(int N, int P[], int S[], int D[]) {
	DP = vl(N);
	G = vvi(N, vi());
	for (int i = 0; i < N-1; i++) {
		G[S[i]].emplace_back(D[i]);
		G[D[i]].emplace_back(S[i]);
		DP[i] = (ll) P[i];
	}
	DP[N-1] = (ll) P[N-1];
	dfs(0, -1);
	int ans = 0;
	ll rec = 0, cur;
	for (int i = 0; i < (int) G[0].size(); i++) {
		rec = max(rec, DP[G[0][i]]);
	}
	int v;
	for (int i = 1; i < N; i++) {
		cur = DP[0] - DP[i];
		for (int j = 0; j < (int) G[i].size(); j++) {
			v = G[i][j];
			if (DP[v] < DP[i]) cur = max(cur, DP[v]);
		}
		if (cur < rec) {
			rec = cur;
			ans = i;
		}
	}
	return ans;
}

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