# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
88890 | 2018-12-09T18:22:09 Z | zviki | Triumphal arch (POI13_luk) | C++14 | 1460 ms | 30596 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 | 9 ms | 7416 KB | Output is correct |
2 | Correct | 9 ms | 7512 KB | Output is correct |
3 | Correct | 8 ms | 7512 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 7512 KB | Output is correct |
2 | Correct | 8 ms | 7544 KB | Output is correct |
3 | Correct | 8 ms | 7544 KB | Output is correct |
4 | Correct | 9 ms | 7556 KB | Output is correct |
5 | Correct | 9 ms | 7572 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 7636 KB | Output is correct |
2 | Correct | 8 ms | 7636 KB | Output is correct |
3 | Correct | 7 ms | 7636 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 7764 KB | Output is correct |
2 | Correct | 9 ms | 7764 KB | Output is correct |
3 | Correct | 10 ms | 7764 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 17 ms | 8088 KB | Output is correct |
2 | Correct | 20 ms | 8228 KB | Output is correct |
3 | Correct | 13 ms | 8228 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 41 ms | 8688 KB | Output is correct |
2 | Correct | 44 ms | 9840 KB | Output is correct |
3 | Correct | 27 ms | 9840 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 214 ms | 11572 KB | Output is correct |
2 | Correct | 159 ms | 15204 KB | Output is correct |
3 | Correct | 75 ms | 15204 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 534 ms | 17488 KB | Output is correct |
2 | Correct | 563 ms | 25316 KB | Output is correct |
3 | Correct | 205 ms | 25316 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1460 ms | 25316 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1156 ms | 25316 KB | Output is correct |
2 | Correct | 1116 ms | 30596 KB | Output is correct |
3 | Correct | 547 ms | 30596 KB | Output is correct |