Submission #758757

#	Time	Username	Problem	Language	Result	Execution time	Memory
758757		SanguineChameleon	Traffic (IOI10_traffic)	C++17	100 / 100	846 ms	156784 KiB

traffic

#include "traffic.h"

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

const int maxn = 1e6 + 20;
vector<int> adj[maxn];
int sum[maxn];
int par[maxn];
int a[maxn];

void dfs(int u) {
	sum[u] = a[u];
	for (auto v: adj[u]) {
		if (v != par[u]) {
			par[v] = u;
			dfs(v);
			sum[u] += sum[v];
		}
	}
}

int LocateCentre(int n, int _a[], int S[], int D[]) {
	for (int i = 1; i <= n; i++) {
		a[i] = _a[i - 1];
	}
	for (int i = 0; i < n - 1; i++) {
		int u = S[i] + 1;
		int v = D[i] + 1;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	par[1] = -1;
	dfs(1);
	pair<int, int> res = make_pair(2e9 + 20, -1);
	for (int u = 1; u <= n; u++) {
		int mx = 0;
		for (auto v: adj[u]) {
			if (v != par[u]) {
				mx = max(mx, sum[v]);
			}
		}
		mx = max(mx, sum[1] - sum[u]);
		res = min(res, make_pair(mx, u));
	}
	return res.second - 1;
}

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