제출 #524993

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
524993		sliviu	Traffic (IOI10_traffic)	C++17	0 / 100	1 ms	304 KiB

traffic

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int LocateCentre(int n, int p[], int s[], int d[]) {
	vector<vector<int>> G(n);
	for (int i = 0; i < n - 1; ++i) {
		G[s[i]].emplace_back(d[i]);
		G[d[i]].emplace_back(s[i]);
	}
	vector<ll> dps(n), dpm(n), dpa(n);
	function<void(int, int)> dfs = [&](int node, int last) {
		dps[node] = p[node];
		for (auto x : G[node])
			if (x != last) {
				dfs(x, node);
				dps[node] += dps[x];
				dpm[node] = max(dpm[node], dps[x]);
			}
	};
	dfs(0, -1);
	ll ans = dpa[0] = dpm[0];
	function<void(int, int)> dfs2 = [&](int node, int last) {
		ans = min(ans, dpa[node]);
		for (auto x : G[node])
			if (x != last) {
				dpa[x] = max(dpm[x], dps[0] - dps[x]);
				dfs2(x, node);
			}
	};
	dfs2(0, -1);
	return ans;
}

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