Submission #356851

#	Time	Username	Problem	Language	Result	Execution time	Memory
356851		penguinhacker	Traffic (IOI10_traffic)	C++14	100 / 100	1317 ms	160876 KiB

traffic

// source: https://oj.uz/problem/view/IOI10_traffic
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

const int mxN = 1000000;
int n, ans, a[mxN], sz[mxN], mx[mxN];
vector<int> adj[mxN];

void dfs(int u = 0, int p = -1) {
	sz[u] = a[u];
	mx[u] = 0;
	for (int v : adj[u]) if (v != p) {
		dfs(v, u);
		sz[u] += sz[v];
		mx[u] = max(mx[u], sz[v]);
	}
}

void dfs2(int u = 0, int p = -1) {
	if (ans == -1 || mx[u] < mx[ans]) ans = u;
	for (int v : adj[u]) if (v != p) {
		mx[v] = max(mx[v], sz[0] - sz[v]);
		dfs2(v, u);
	}
}

int LocateCentre(int _n, int p[], int s[], int d[]) {
	n = _n;
	for (int i = 0; i < n; ++i) a[i] = p[i];
	for (int i = 0; i < n - 1; ++i) {
		adj[s[i]].push_back(d[i]);
		adj[d[i]].push_back(s[i]);
	}
	ans = -1;
	dfs();
	dfs2();
	// for (int i = 0; i < n; ++i) cout << mx[i] << " ";
	return ans;
}

/*
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n = 5;
	int p[5] = {10, 10, 10, 20, 20};
	int s[4] = {0, 1, 2, 3};
	int d[4] = {2, 2, 3, 4};
	cout << LocateCentre(n, p, s, d);
	return 0;
}
*/

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