Submission #406565

#	Time	Username	Problem	Language	Result	Execution time	Memory
406565		benk	Traffic (IOI10_traffic)	C++14	100 / 100	1129 ms	141392 KiB

traffic

#include "traffic.h"
#include <bits/stdc++.h>
using namespace std;

#define pb	push_back
const int N = 1e6 + 10;

int tot;
vector<int> adj[N], ch(N), peop(N), curr(N);
vector<bool> vis(N);
void dfs(int x) {
	vis[x] = 1;
	for (auto it : adj[x]) {
		if (vis[it]) continue;
		dfs(it);
		ch[x] += ch[it];
		peop[x] = max(peop[x], ch[it]); // max of all ch
	}
	ch[x] += curr[x];
	peop[x] = max(peop[x], tot - ch[x]); // either from par or ch
}

int LocateCentre(int n, int p[], int s[], int d[]) {
	for (int i = 0; i < n - 1; i++) {
		adj[s[i]].pb(d[i]);
		adj[d[i]].pb(s[i]);
	}

	for (int i = 0; i < n; i++) {
		tot += p[i];
		curr[i] = p[i];
	}
	dfs(0);
	int ans = INT_MAX, res = -1;
	for (int i = 0; i < n; i++) {
		if (ans > peop[i]) {
			ans = peop[i];
			res = i;
		}
	}

	return res;
}

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