제출 #1018882

#제출 시각아이디문제언어결과실행 시간메모리
1018882socpiteTraffic (IOI10_traffic)C++14
0 / 100
10 ms23900 KiB
#include "traffic.h" #include <bits/stdc++.h> using namespace std; const int maxn = 1e6+5; const long long INF = 1e18; vector<int> g[maxn]; long long sz[maxn], mx[maxn]; int dfs(int x, int p, long long tot){ int re = 0; mx[x] = 0; for(auto v: g[x]){ if(v == p)continue; int tmp = dfs(v, x, tot); sz[x] += sz[v]; mx[x] = max(mx[x], sz[v]); if(mx[tmp] < mx[re])re = tmp; } mx[x] = max(mx[x], tot - sz[x]); if(mx[x] < mx[re])re = x; return re; } int LocateCentre(int N, int pp[], int S[], int D[]) { mx[0] = INF; long long sum = 0; for(int i = 0; i < N; i++){ g[i].clear(); sz[i] = pp[i]; sum += pp[i]; } for(int i = 0; i < N-1; i++){ g[S[i]].push_back(D[i]); g[D[i]].push_back(S[i]); } return dfs(0, -1, sum); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...