# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
203241 | 2020-02-19T22:02:53 Z | MKopchev | Triumphal arch (POI13_luk) | C++14 | 893 ms | 26488 KB |
#include<bits/stdc++.h> using namespace std; const int nmax=3e5+42; int n; vector<int> adj[nmax]; int MX; int dfs(int node,int parent) { int adj_size=0,more=0; for(auto k:adj[node]) if(k!=parent) { adj_size++; more=more+dfs(k,node); } int ret=adj_size+more-MX; ret=max(ret,0); return ret; } bool can(int current) { MX=current; return dfs(1,0)==0; } int main() { scanf("%i",&n); int u,v; for(int i=1;i<n;i++) { scanf("%i%i",&u,&v); adj[u].push_back(v); adj[v].push_back(u); } int ok=n-1,not_ok=-1; while(ok-not_ok>1) { int av=(ok+not_ok)/2; if(can(av))ok=av; else not_ok=av; } printf("%i\n",ok); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 9 ms | 7288 KB | Output is correct |
2 | Correct | 9 ms | 7288 KB | Output is correct |
3 | Correct | 9 ms | 7288 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 9 ms | 7288 KB | Output is correct |
2 | Correct | 9 ms | 7416 KB | Output is correct |
3 | Correct | 9 ms | 7416 KB | Output is correct |
4 | Correct | 9 ms | 7416 KB | Output is correct |
5 | Correct | 9 ms | 7416 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 10 ms | 7416 KB | Output is correct |
2 | Correct | 9 ms | 7416 KB | Output is correct |
3 | Correct | 9 ms | 7416 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 9 ms | 7416 KB | Output is correct |
2 | Correct | 10 ms | 7288 KB | Output is correct |
3 | Correct | 9 ms | 7416 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 16 ms | 7672 KB | Output is correct |
2 | Correct | 17 ms | 8056 KB | Output is correct |
3 | Correct | 14 ms | 7800 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 36 ms | 8312 KB | Output is correct |
2 | Correct | 34 ms | 9592 KB | Output is correct |
3 | Correct | 25 ms | 8836 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 160 ms | 10744 KB | Output is correct |
2 | Correct | 145 ms | 13688 KB | Output is correct |
3 | Correct | 66 ms | 12152 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 474 ms | 14072 KB | Output is correct |
2 | Correct | 489 ms | 21240 KB | Output is correct |
3 | Correct | 165 ms | 17144 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 861 ms | 17400 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 857 ms | 17400 KB | Output is correct |
2 | Correct | 893 ms | 26488 KB | Output is correct |
3 | Correct | 308 ms | 22136 KB | Output is correct |