Submission #406513

#	Time	Username	Problem	Language	Result	Execution time	Memory
406513		benk	Traffic (IOI10_traffic)	C++14	0 / 100	200 ms	262148 KiB

traffic

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

#define all(x)      x.begin(), x.end()
#define pb          push_back
#define sz(x)       (int)(x.size())
#define ll          long long
#define fi          first
#define se          second
#define lbd         lower_bound
#define ubd         upper_bound

const int MOD = 1e9 + 7;
const double eps = 1e-10;
const long long INF = 1e18;
const int N = 1e6 + 10;

int tot;
vector<int> adj[N], ch(N), peop(N);
vector<bool> vis(N);
void dfs(int x, int p[]) {
	vis[x] = 1;
	for (auto it : adj[x]) {
		vis[it] = 1;
		dfs(it, p);
		ch[x] += ch[it];
		peop[x] = max(peop[x], ch[x]); // max of all ch
	}
	ch[x] += p[x];
	peop[x] = max(peop[x], tot - ch[x]); // either from ancestors 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];
	dfs(0, p);
	ll 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: 0 / 25
• Subtask 2: 0 / 25
• Subtask 3: 0 / 25
• Subtask 4: 0 / 25