# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
45308 | 2018-04-12T19:41:57 Z | imaxblue | Triumphal arch (POI13_luk) | C++17 | 1181 ms | 32104 KB |
#include <bits/stdc++.h> using namespace std; #define ll long long #define mp make_pair #define pb push_back #define x first #define y second #define pii pair<int, int> #define p3i pair<pii, int> #define pll pair<ll, ll> #define p3l pair<pll, ll> #define vi vector<int> #define vpii vector<pii> #define vp3i vector<p3i> #define vpll vector<pll> #define vp3l vector<p3l> #define lseg L, (L+R)/2, N*2+1 #define rseg (L+R)/2+1, R, N*2+2 #define ub upper_bound #define lb lower_bound #define pq priority_queue #define MN 1000000007 #define fox(k, x) for (int k=0; k<x; ++k) #define fox1(k, x) for (int k=1; k<=x; ++k) #define foxr(k, x) for (int k=x-1; k>=0; --k) #define fox1r(k, x) for (int k=x; k>0; --k) #define ms multiset #define flood(x) memset(x, 0x3f3f3f3f, sizeof x) #define drain(x) memset(x, 0, sizeof x) #define rng() ((rand() << 14)+rand()) #define scan(X) do{while((X=getchar())<'0'); for(X-='0'; '0'<=(_=getchar()); X=(X<<3)+(X<<1)+_-'0');}while(0) char _; #define pi 3.14159265358979323846 #define siz(x) int(x.size()) int n, x, y, lo, mid, hi=300000; vector<int> v[300005]; bool dfs(int N, ll D, int P){ D=D+mid-siz(v[N])+(P!=-1); if (D<0) return 0; fox(l, v[N].size()){ if (v[N][l]==P) continue; if (!dfs(v[N][l], D, N)) return 0; } return 1; } int32_t main(){ scanf("%i", &n); fox(l, n-1){ scanf("%i%i", &x, &y); v[x].pb(y); v[y].pb(x); } while(lo<hi){ mid=(lo+hi)/2; if (dfs(1, 0, -1)) hi=mid; else lo=mid+1; } mid=150000; //cout << dfs(1, 0, -1) << endl; cout << lo; return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 7416 KB | Output is correct |
2 | Correct | 8 ms | 7536 KB | Output is correct |
3 | Correct | 8 ms | 7592 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 7592 KB | Output is correct |
2 | Correct | 8 ms | 7600 KB | Output is correct |
3 | Correct | 8 ms | 7696 KB | Output is correct |
4 | Correct | 7 ms | 7696 KB | Output is correct |
5 | Correct | 2 ms | 7748 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 7788 KB | Output is correct |
2 | Correct | 7 ms | 7788 KB | Output is correct |
3 | Correct | 7 ms | 7796 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 8 ms | 7816 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 18 ms | 8208 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 39 ms | 9216 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 149 ms | 12740 KB | Output is correct |
2 | Correct | 238 ms | 15740 KB | Output is correct |
3 | Incorrect | 65 ms | 15740 KB | Output isn't correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 682 ms | 20976 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 1181 ms | 28064 KB | Output isn't correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 925 ms | 32104 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |