Submission #356849

#	Time	Username	Problem	Language	Result	Execution time	Memory
356849		penguinhacker	Traffic (IOI10_traffic)	C++14	0 / 100	2 ms	2668 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 = 100000;
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], mx[0] - mx[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();
	return ans + 1;
}

/*int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	return 0;
}*/

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