# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
90828 | 2018-12-24T17:22:29 Z | Vardanyan | Triumphal arch (POI13_luk) | C++14 | 322 ms | 32992 KB |
#include<bits/stdc++.h> using namespace std; const int N = 300*1000+5; int depth[N]; vector<int> g[N]; void dfs(int v,int p = 0){ depth[v] = depth[p]+1; for(int i = 0;i<g[v].size();i++){ int to = g[v][i]; if(to == p) continue; dfs(to,v); } } vector<int> all; bool check(int crew){ int tim = 1; int pos = 0; while(pos<all.size()){ for(int i = 0;i<crew;i++){ if(all[pos]<=tim) return false; pos++; if(pos>=all.size()) return true; } tim++; } return true; } int main() { int n; scanf("%d",&n); for(int i = 1;i<=n-1;i++){ int x,y; scanf("%d%d",&x,&y); g[x].push_back(y); g[y].push_back(x); } if(n == 1){ printf("0\n"); return 0; } dfs(1); for(int i = 2;i<=n;i++){ all.push_back(depth[i]); } sort(all.begin(),all.end()); int l = 1; int r = n; int ans = n-1; while(l<=r){ int m = (l+r)/2; if(check(m)){ ans = m; r = m-1; } else l = m+1; } printf("%d\n",ans); return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 7416 KB | Output is correct |
2 | Correct | 7 ms | 7496 KB | Output is correct |
3 | Incorrect | 7 ms | 7560 KB | Output isn't correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 7 ms | 7560 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 6 ms | 7604 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 7 ms | 7632 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 11 ms | 8152 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 21 ms | 9416 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 65 ms | 13616 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 186 ms | 20396 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 322 ms | 29028 KB | Output isn't correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 316 ms | 32992 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |