# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
254236 | 2020-07-29T15:13:35 Z | tatyam | Traffic (IOI10_traffic) | C++17 | 0 ms | 0 KB |
#include <bits/stdc++.h> using namespace std; template<class T, class U> bool chmax(T& a, const U& b){ if(a < b){ a = b; return 1; } return 0; } int LocateCentre(int n, int p[], int s[], int d[]){ const int sum = reduce(p, p + n, 0); vector<vector<int>> g(n); for(int i = 0; i < n - 1; i++){ const int a = s[i], b = d[i]; g[a].push_back(b); g[b].push_back(a); } vector<int> siz(n, 1), dp(n); auto dfs = [&](int from, int at, const auto& dfs) -> void { for(int i : g[at]) if(i != from){ dfs(at, i, dfs); chmax(dp[at], siz[i]); siz[at] += siz[i]; } chmax(dp[at], sum - siz[at]); }; dfs(-1, 0, dfs); return min_element(dp.begin(), dp.end()) - dp.begin(); }