# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
28986 | 2017-07-18T02:50:11 Z | 서규호 (지각충1)(#1231) | Triumphal arch (POI13_luk) | C++14 | 1253 ms | 19244 KB |
#include <bits/stdc++.h> #include <unistd.h> #define pii pair<int,int> #define pll pair<lld,lld> #define pb push_back #define next nextt #define lld long long #define Inf 1000000000 #define Linf 1000000000000000000LL #define get gett using namespace std; int N,ans; bool check[300002]; vector<int> edge[300002]; int add; bool flag; void dfs(int x,lld left){ check[x] = true; int child = 0; for(auto &i : edge[x]){ if(check[i]) continue; child++; } if(left < child){ flag = false; return; } for(auto &i : edge[x]){ if(check[i]) continue; dfs(i,left-child+add); } } bool can(int x){ add = x; for(int i=1; i<=N; i++) check[i] = false; flag = true; dfs(1,x); return flag; } int main(){ scanf("%d",&N); for(int i=1; i<N; i++){ int x,y; scanf("%d %d",&x,&y); edge[x].pb(y); edge[y].pb(x); } int l,r; l = 0; r = N-1; while(l <= r){ int m = (l+r)>>1; if(can(m)){ ans = m; r = m-1; }else l = m+1; } printf("%d\n",ans); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 9344 KB | Output is correct |
2 | Correct | 0 ms | 9344 KB | Output is correct |
3 | Correct | 0 ms | 9344 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 9344 KB | Output is correct |
2 | Correct | 3 ms | 9344 KB | Output is correct |
3 | Correct | 0 ms | 9344 KB | Output is correct |
4 | Correct | 0 ms | 9344 KB | Output is correct |
5 | Correct | 0 ms | 9344 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 9344 KB | Output is correct |
2 | Correct | 3 ms | 9344 KB | Output is correct |
3 | Correct | 0 ms | 9344 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 3 ms | 9344 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 9 ms | 9740 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 29 ms | 10400 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 166 ms | 12644 KB | Output is correct |
2 | Correct | 156 ms | 13384 KB | Output is correct |
3 | Incorrect | 116 ms | 13044 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 516 ms | 15944 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 663 ms | 19244 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1253 ms | 19244 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |