제출 #493021

#제출 시각아이디문제언어결과실행 시간메모리
493021JooDdaeTraffic (IOI10_traffic)C++17
0 / 100
12 ms23756 KiB
#include <bits/stdc++.h> #include "traffic.h" using namespace std; using ll = long long; vector<int> v[1001001]; int n, sz[1001001]; int dfs(int u, int p){ for(auto x : v[u]) if(x != p) sz[u] += dfs(x, u); return sz[u]; } pair<int, int> dfs2(int u, int p){ pair<int, int> re = {n-sz[u], u}; for(auto x : v[u]) if(x != p) re.first = max(re.first, sz[x]); for(auto x : v[u]) if(x != p) re = min(re, dfs2(x, u)); return re; } int LocateCentre(int N, int pp[], int S[], int D[]) { n = N; for(int i=0;i<N-1;i++) v[S[i]].push_back(D[i]), v[D[i]].push_back(S[i]); dfs(0, 0); return dfs2(0, 0).second; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...