제출 #296425

#제출 시각아이디문제언어결과실행 시간메모리
296425moratoTraffic (IOI10_traffic)C++17
0 / 100
17 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]; 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]); } } 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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...