# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
28941 | 2017-07-18T01:38:07 Z | khsoo01 | Triumphal arch (POI13_luk) | C++11 | 1193 ms | 23796 KB |
#include<bits/stdc++.h> using namespace std; const int N = 300005; int n, v[N], cur; vector<int> adj[N]; void solve (int C, int P) { v[C] = cur - (int)adj[C].size() + !!P; for(auto &T : adj[C]) { if(T == P) continue; solve(T, C); if(v[T] < 0) v[C] += v[T]; } } int main() { scanf("%d",&n); for(int i=1;i<n;i++) { int A, B; scanf("%d%d",&A,&B); adj[A].push_back(B); adj[B].push_back(A); } int S = 0, E = n; while(S < E) { int M = (S+E)/2; cur = M; solve(1, 0); v[1] < 0 ? S = M+1 : E = M; } printf("%d\n",S); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 10224 KB | Output is correct |
2 | Correct | 0 ms | 10224 KB | Output is correct |
3 | Correct | 3 ms | 10224 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 10224 KB | Output is correct |
2 | Correct | 0 ms | 10224 KB | Output is correct |
3 | Correct | 3 ms | 10224 KB | Output is correct |
4 | Correct | 0 ms | 10224 KB | Output is correct |
5 | Correct | 0 ms | 10224 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 10224 KB | Output is correct |
2 | Correct | 0 ms | 10224 KB | Output is correct |
3 | Correct | 0 ms | 10224 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 10224 KB | Output is correct |
2 | Correct | 0 ms | 10224 KB | Output is correct |
3 | Correct | 3 ms | 10224 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 9 ms | 10620 KB | Output is correct |
2 | Correct | 6 ms | 10660 KB | Output is correct |
3 | Correct | 3 ms | 10620 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 36 ms | 11280 KB | Output is correct |
2 | Correct | 43 ms | 11716 KB | Output is correct |
3 | Correct | 23 ms | 11412 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 186 ms | 13524 KB | Output is correct |
2 | Correct | 193 ms | 14760 KB | Output is correct |
3 | Correct | 113 ms | 13924 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 583 ms | 16824 KB | Output is correct |
2 | Correct | 459 ms | 20072 KB | Output is correct |
3 | Correct | 206 ms | 17632 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1193 ms | 20124 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1026 ms | 20124 KB | Output is correct |
2 | Correct | 1176 ms | 23796 KB | Output is correct |
3 | Correct | 436 ms | 21160 KB | Output is correct |