# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
289677 | 2020-09-02T22:35:39 Z | Farrius | Traffic (IOI10_traffic) | C++11 | 0 ms | 0 KB |
#include <bits/stdc++.h> using namespace std; const int MX = 1e6; const int INF = 2e9 + 1; int fans = 0; vector<int> g[MX], nodes(MX), people(MX), children(MX); int dfs (int v, int parent) { for (auto x: g[v]) { if (x == parent) continue; int k = dfs(x, v); children[v] += children[x]; people[v] = max(people[v], k); } people[v] = max(people[v], fans - children[v] - nodes[v]); children[v] += nodes[v]; } int LocateCentre (int n, vector<int>& p, vector<int>& s, vector<int>& d) { for (int i = 0; i < n; i++) { fans += p[i]; nodes[i] = p[i]; } for (int i = 0; i < n - 1; i++) { g[s[i]].push_back(d[i]); g[d[i]].push_back(s[i]); } dfs(0, -1); int sol = INF, res = -1; for (int i = 0; i < n; i++) { if (people[i] < sol) { res = i; sol = people[i]; } } return res; }