Submission #919876

#TimeUsernameProblemLanguageResultExecution timeMemory
919876boris_mihovTraffic (IOI10_traffic)C++17
0 / 100
9 ms31324 KiB
#include "traffic.h" #include <algorithm> #include <iostream> #include <numeric> #include <cassert> #include <vector> typedef long long llong; const int MAXN = 1e6 + 10; const int INF = 1e9; int n; int sz[MAXN]; std::vector <int> g[MAXN]; void dfs(int node, int par) { sz[node] = 1; for (const int &u : g[node]) { if (u == par) { continue; } dfs(u, node); sz[node] += sz[u]; } } int find(int node, int par) { for (const int &u : g[node]) { if (u == par) { continue; } if (sz[u] > n / 2) { return find(u, node); } } return node; } int LocateCentre(int N, int pp[], int S[], int D[]) { n = N; 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); return find(0, -1); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...