# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
384997 | 2021-04-02T21:27:48 Z | ritul_kr_singh | Traffic (IOI10_traffic) | C++17 | 0 ms | 0 KB |
#include <bits/stdc++.h> #include "traffic.h" using namespace std; const int MAXN = 1e6; vector<vector<int>> g; int sub[MAXN], sum = 0, curr = 0, ans = 1e18; void dfs0(int u, int par){ for(int v : g[u]) if(v != par){ sub[u] += dfs0(v, u); curr = max(curr, sub[v]); } return sub[u]; } void dfs1(int u, int par){ ans = min(ans, curr); for(int v : g[u]){ if(v==par) continue; int prev = curr; curr = max(curr, sum - sub[v]); dfs1(v, u); curr = prev; } } int LocateCentre(int n, int pop[], int S[], int D[]){ for(int i=0; i<n; ++i) sum += (sub[i] = pop[i]); g.resize(n); for(int i=0; i<n-1; ++i){ g[S[i]].push_back(D[i]); g[D[i]].push_back(S[i]); } dfs0(0, 0); dfs1(0, 0); return ans; }