Submission #373315

#	Time	Username	Problem	Language	Result	Execution time	Memory
373315		No_Ice	Traffic (IOI10_traffic)	C++17	100 / 100	1172 ms	159096 KiB

traffic

#include "traffic.h"
#include <bits/stdc++.h>

using namespace std;

const int mxN = 1e6;
const int INF = 1e9 + 5;

int fans;
vector<int> adj[mxN], nodes(mxN), people(mxN), children(mxN);

void dfs(int u, int parent) {
	for (int v : adj[u]) {
		if (v == parent) continue;

		dfs(v, u);
		children[u] += children[v];
		people[u] = max(people[u], children[v]);
	}

	people[u] = max(people[u], fans - nodes[u] - children[u]);
	children[u] += nodes[u];
}

int LocateCentre(int N, int P[], int S[], int D[]) {
	for (int i=0; i < N; i++) {
		nodes[i] = P[i];
		fans += P[i];
	}

	for (int i=0; i < N-1; i++) {
		adj[S[i]].push_back(D[i]);
		adj[D[i]].push_back(S[i]);
	}

	dfs(0, -1);

	int ans = INF, a1 = 0;
	for (int i=0; i < N; i++) {
		if (people[i] < ans) {
			ans = people[i];
			a1 = i;
		}
	}

	return a1;
}

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