Submission #308288

#	Time	Username	Problem	Language	Result	Execution time	Memory
308288		Temmie	Traffic (IOI10_traffic)	C++17	100 / 100	1260 ms	153208 KiB

traffic

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

std::vector <std::vector <int>> g;
std::vector <int> ans, sms;
int sum = 0;

void dfs(int val[], int node = 0, int par = -1) {
	sms[node] = val[node];
	for (int x : g[node]) if (x != par) {
		dfs(val, x, node);
		sms[node] += sms[x];
		ans[node] = std::max(ans[node], sms[x]);
	}
	ans[node] = std::max(ans[node], sum - sms[node]);
}

int LocateCentre(int n, int val[], int u[], int v[]) {
	for (int i = 0; i < n; i++) sum += val[i];
	g.resize(n);
	ans.resize(n, 0);
	sms.resize(n, 0);
	for (int i = 0; i < n - 1; i++) {
		g[u[i]].push_back(v[i]);
		g[v[i]].push_back(u[i]);
	}
	dfs(val);
	int ansind = 0, best = INT_MAX;
	for (int i = 0; i < n; i++) {
		if (ans[i] < best) {
			best = ans[i];
			ansind = i;
		}
	}
	return ansind;
}

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