# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
317022 | 2020-10-29T01:07:01 Z | nandonathaniel | Traffic (IOI10_traffic) | C++14 | 15 ms | 23808 KB |
#include "traffic.h" #include <bits/stdc++.h> using namespace std; const int MAXN=1e6+5; vector<int> adj[MAXN]; int subtree[MAXN],atas[MAXN]; void dfs(int now,int par){ atas[now]=par; for(auto nxt : adj[now]){ if(nxt==par)continue; dfs(nxt,now); subtree[now]+=subtree[nxt]; } } int LocateCentre(int N, int P[], int S[], int D[]) { for(int i=0;i<N;i++)subtree[i]=P[i]; for(int i=0;i<N-1;i++){ adj[S[i]].push_back(D[i]); adj[D[i]].push_back(S[i]); } dfs(0,-1); int ans=1e9,idx; for(int i=0;i<N;i++){ int ret=0; for(auto j : adj[i]){ if(j==atas[i])ret=max(ret,N-subtree[i]); else ret=max(ret,subtree[j]); } if(ret<ans){ ans=ret; idx=i; } } return idx; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 15 ms | 23808 KB | Output is correct |
2 | Incorrect | 15 ms | 23808 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 15 ms | 23808 KB | Output is correct |
2 | Incorrect | 15 ms | 23808 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 15 ms | 23808 KB | Output is correct |
2 | Incorrect | 15 ms | 23808 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 15 ms | 23808 KB | Output is correct |
2 | Incorrect | 15 ms | 23808 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |