Submission #406523

#	Time	Username	Problem	Language	Result	Execution time	Memory
406523		benk	Traffic (IOI10_traffic)	C++14	50 / 100	569 ms	158976 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), 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[x]); // max of all ch
	}
	ch[x] += curr[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];
		curr[i] = p[i];
	}
	dfs(0);
	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: 25 / 25
• Subtask 2: 25 / 25
• Subtask 3: 0 / 25
• Subtask 4: 0 / 25