# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
296424 | 2020-09-10T14:33:18 Z | morato | Traffic (IOI10_traffic) | C++17 | 0 ms | 0 KB |
#include <bits/stdc++.h> using namespace std; const int maxn = 1e6 + 5; vector<int> adj[maxn]; int64_t p[maxn], h[maxn], sub[maxn]; void dfs(int v, int _p = -1) { sub[v] = p[v]; for (int u : adj[v]) if (u != _p) { dfs(u, v); sub[v] += sub[u]; h[v] = max(h[v], sub[u]); } return sub[v]; } int LocateCentre(int N, int P[], int S[], int D[]) { for (int i = 0; i < N; i++) { p[i] = 1ll * P[i]; } for (int i = 0; i < N; i++) { adj[S[i]].push_back(D[i]); adj[D[i]].push_back(S[i]); } int ans = 0; int64_t heavy = h[0]; for (int i = 1; i < N; i++) { h[i] = max(h[i], sub[0] - sub[i]); if (h[i] < heavy) { heavy = h[i]; ans = i; } } return ans; }