# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
317020 | 2020-10-29T01:05:59 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-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
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 15 ms | 23808 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 15 ms | 23808 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 15 ms | 23808 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 15 ms | 23808 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |