# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
28945 | 2017-07-18T01:46:27 Z | 김동현(#1232) | Triumphal arch (POI13_luk) | C++14 | 1026 ms | 18952 KB |
#include <bits/stdc++.h> using namespace std; int n; vector<int> e[300010]; int f(int x, int p, int c, int s){ int t = int(e[x].size()) - !!p; if(t > c) return 0; for(auto &i : e[x]){ if(i != p && !f(i, x, c - t + s, s)) return 0; } return 1; } int can(int x){ return f(1, 0, x, x); } int main(){ scanf("%d", &n); for(int i = 0, x, y; i < n - 1; i++){ scanf("%d%d", &x, &y); e[x].push_back(y); e[y].push_back(x); } int s = int(e[1].size()), e = n - 1; while(s <= e){ int m = (s + e) / 2; if(can(m)) e = m - 1; else s = m + 1; } printf("%d\n", s); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 9052 KB | Output is correct |
2 | Correct | 0 ms | 9052 KB | Output is correct |
3 | Correct | 0 ms | 9052 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 9052 KB | Output is correct |
2 | Correct | 0 ms | 9052 KB | Output is correct |
3 | Correct | 0 ms | 9052 KB | Output is correct |
4 | Correct | 0 ms | 9052 KB | Output is correct |
5 | Correct | 3 ms | 9052 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 9052 KB | Output is correct |
2 | Correct | 0 ms | 9052 KB | Output is correct |
3 | Correct | 0 ms | 9052 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 0 ms | 9052 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 9 ms | 9448 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 33 ms | 10108 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 206 ms | 12352 KB | Output is correct |
2 | Correct | 186 ms | 14088 KB | Output is correct |
3 | Incorrect | 69 ms | 12752 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 616 ms | 15652 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1022 ms | 18952 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1026 ms | 18952 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |