제출 #296419

#제출 시각아이디문제언어결과실행 시간메모리
296419moratoTraffic (IOI10_traffic)C++17
0 / 100
16 ms23808 KiB
#include <bits/stdc++.h> using namespace std; const int maxn = 1e6 + 5; vector<int> adj[maxn]; int64_t p[maxn], h[maxn], sub[maxn], tot; int64_t dfs(int v, int _p = -1) { sub[v] = p[v]; for (int u : adj[v]) if (u != _p) { int64_t wgt = dfs(u, v); sub[v] += wgt; h[v] = max(h[v], wgt); } return sub[v]; } int LocateCentre(int N, int P[], int S[], int D[]) { for (int i = 0; i < N; i++) { p[i] = P[i]; } for (int i = 0; i < N; i++) { adj[S[i]].push_back(D[i]); adj[D[i]].push_back(S[i]); } dfs(0); 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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...