# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
88868 | 2018-12-09T13:26:05 Z | 123456 | Triumphal arch (POI13_luk) | C++14 | 1586 ms | 25404 KB |
#include <bits/stdc++.h> using namespace std; int n; vector < int > G[300020]; int answer[300020]; void go(int v, int p, int x){ int tot = 0; for(int i = 0; i < G[v].size(); ++ i){ if(G[v][i] == p) continue; go(G[v][i], v, x); tot += answer[G[v][i]] + 1; } answer[v] = max(0, tot - x); } int main(){ scanf("%d", &n); for(int i = 1; i < n; ++ i){ int x, y; scanf("%d %d", &x, &y); G[x].push_back(y); G[y].push_back(x); } int l = 0; int r = n; while(l < r){ int mid = (l + r) / 2; go(1, 0, mid); if(answer[1]) l = mid + 1; else r = mid; } printf("%d", l); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 10 ms | 7416 KB | Output is correct |
2 | Correct | 8 ms | 7420 KB | Output is correct |
3 | Correct | 9 ms | 7464 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 7464 KB | Output is correct |
2 | Correct | 8 ms | 7544 KB | Output is correct |
3 | Correct | 8 ms | 7548 KB | Output is correct |
4 | Correct | 8 ms | 7600 KB | Output is correct |
5 | Correct | 9 ms | 7600 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 7600 KB | Output is correct |
2 | Correct | 8 ms | 7600 KB | Output is correct |
3 | Correct | 8 ms | 7600 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 7660 KB | Output is correct |
2 | Correct | 9 ms | 7660 KB | Output is correct |
3 | Correct | 9 ms | 7696 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 18 ms | 7916 KB | Output is correct |
2 | Correct | 19 ms | 8304 KB | Output is correct |
3 | Correct | 14 ms | 8304 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 41 ms | 8700 KB | Output is correct |
2 | Correct | 43 ms | 9852 KB | Output is correct |
3 | Correct | 27 ms | 9852 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 179 ms | 11376 KB | Output is correct |
2 | Correct | 186 ms | 13820 KB | Output is correct |
3 | Correct | 75 ms | 13820 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 765 ms | 15100 KB | Output is correct |
2 | Correct | 672 ms | 20940 KB | Output is correct |
3 | Correct | 325 ms | 20940 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1476 ms | 20940 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1391 ms | 20940 KB | Output is correct |
2 | Correct | 1586 ms | 25404 KB | Output is correct |
3 | Correct | 486 ms | 25404 KB | Output is correct |