/******************************************************************************
Online C++ Compiler.
Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.
*******************************************************************************/
#include <bits/stdc++.h>
using namespace std;
const int INF = INT32_MAX;
int N, T, M, P[1000005], rem[1000005];
int DP[1000005], deg[1000005], S[1000005];
vector<int> adj[1000005], C[1000005];
void dfs(int v, int p) {
if(v == M) rem[v] = 1;
for(auto u : adj[v]) {
if(u == p) continue;
dfs(u, v); P[u] = v;
if(rem[u]) rem[v] = 1;
else {
C[v].push_back(u); ++deg[v];
}
}
sort(C[v].begin(), C[v].end(), [](int A, int B) { return DP[A] > DP[B]; });
if(C[v].size() <= 1) DP[v] = deg[v];
else DP[v] = deg[v] + DP[C[v][1]];
}
void dfs(int v) {
DP[v] += S[v];
for(auto u : adj[v]) {
if(u == P[v]) continue;
S[u] = S[v] + deg[v]; dfs(u);
}
}
bool possible(int v) {
int cur = 0, dep = 0;
for(int e = M; e != T; e = P[e]) {
++dep; int k = 0;
for(auto u : C[e]) {
if(DP[u] + cur - k > v) ++cur, ++k;
}
if(cur > dep || cur > v)
return false;
}
return true;
}
int32_t main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> N >> T >> M;
for(int l = 0; l < N - 1; l++) {
int U, V; cin >> U >> V;
adj[U].push_back(V);
adj[V].push_back(U);
}
dfs(T, T); deg[T] = 0; dfs(T);
int lo = 0, hi = N, ans = -1;
while(lo <= hi) {
int md = (lo + hi) / 2;
if(possible(md)) ans = md, hi = md - 1;
else lo = md + 1;
}
cout << ans << "\n";
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
23 ms |
47316 KB |
Output is correct |
| 2 |
Correct |
24 ms |
47316 KB |
Output is correct |
| 3 |
Correct |
27 ms |
47236 KB |
Output is correct |
| 4 |
Correct |
24 ms |
47308 KB |
Output is correct |
| 5 |
Correct |
23 ms |
47276 KB |
Output is correct |
| 6 |
Correct |
23 ms |
47292 KB |
Output is correct |
| 7 |
Correct |
23 ms |
47312 KB |
Output is correct |
| 8 |
Correct |
23 ms |
47316 KB |
Output is correct |
| 9 |
Correct |
22 ms |
47236 KB |
Output is correct |
| 10 |
Correct |
22 ms |
47292 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
343 ms |
107932 KB |
Output is correct |
| 2 |
Correct |
302 ms |
102456 KB |
Output is correct |
| 3 |
Correct |
962 ms |
112144 KB |
Output is correct |
| 4 |
Correct |
457 ms |
80000 KB |
Output is correct |
| 5 |
Correct |
969 ms |
112076 KB |
Output is correct |
| 6 |
Correct |
1006 ms |
112308 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
23 ms |
47316 KB |
Output is correct |
| 2 |
Correct |
24 ms |
47316 KB |
Output is correct |
| 3 |
Correct |
27 ms |
47236 KB |
Output is correct |
| 4 |
Correct |
24 ms |
47308 KB |
Output is correct |
| 5 |
Correct |
23 ms |
47276 KB |
Output is correct |
| 6 |
Correct |
23 ms |
47292 KB |
Output is correct |
| 7 |
Correct |
23 ms |
47312 KB |
Output is correct |
| 8 |
Correct |
23 ms |
47316 KB |
Output is correct |
| 9 |
Correct |
22 ms |
47236 KB |
Output is correct |
| 10 |
Correct |
22 ms |
47292 KB |
Output is correct |
| 11 |
Correct |
23 ms |
47316 KB |
Output is correct |
| 12 |
Correct |
22 ms |
47396 KB |
Output is correct |
| 13 |
Correct |
24 ms |
47316 KB |
Output is correct |
| 14 |
Correct |
27 ms |
47564 KB |
Output is correct |
| 15 |
Correct |
24 ms |
47428 KB |
Output is correct |
| 16 |
Correct |
26 ms |
47320 KB |
Output is correct |
| 17 |
Correct |
24 ms |
47280 KB |
Output is correct |
| 18 |
Correct |
25 ms |
47316 KB |
Output is correct |
| 19 |
Correct |
23 ms |
47316 KB |
Output is correct |
| 20 |
Correct |
24 ms |
47316 KB |
Output is correct |
| 21 |
Correct |
24 ms |
47316 KB |
Output is correct |
| 22 |
Correct |
23 ms |
47356 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
23 ms |
47316 KB |
Output is correct |
| 2 |
Correct |
24 ms |
47316 KB |
Output is correct |
| 3 |
Correct |
27 ms |
47236 KB |
Output is correct |
| 4 |
Correct |
24 ms |
47308 KB |
Output is correct |
| 5 |
Correct |
23 ms |
47276 KB |
Output is correct |
| 6 |
Correct |
23 ms |
47292 KB |
Output is correct |
| 7 |
Correct |
23 ms |
47312 KB |
Output is correct |
| 8 |
Correct |
23 ms |
47316 KB |
Output is correct |
| 9 |
Correct |
22 ms |
47236 KB |
Output is correct |
| 10 |
Correct |
22 ms |
47292 KB |
Output is correct |
| 11 |
Correct |
343 ms |
107932 KB |
Output is correct |
| 12 |
Correct |
302 ms |
102456 KB |
Output is correct |
| 13 |
Correct |
962 ms |
112144 KB |
Output is correct |
| 14 |
Correct |
457 ms |
80000 KB |
Output is correct |
| 15 |
Correct |
969 ms |
112076 KB |
Output is correct |
| 16 |
Correct |
1006 ms |
112308 KB |
Output is correct |
| 17 |
Correct |
23 ms |
47316 KB |
Output is correct |
| 18 |
Correct |
22 ms |
47396 KB |
Output is correct |
| 19 |
Correct |
24 ms |
47316 KB |
Output is correct |
| 20 |
Correct |
27 ms |
47564 KB |
Output is correct |
| 21 |
Correct |
24 ms |
47428 KB |
Output is correct |
| 22 |
Correct |
26 ms |
47320 KB |
Output is correct |
| 23 |
Correct |
24 ms |
47280 KB |
Output is correct |
| 24 |
Correct |
25 ms |
47316 KB |
Output is correct |
| 25 |
Correct |
23 ms |
47316 KB |
Output is correct |
| 26 |
Correct |
24 ms |
47316 KB |
Output is correct |
| 27 |
Correct |
24 ms |
47316 KB |
Output is correct |
| 28 |
Correct |
23 ms |
47356 KB |
Output is correct |
| 29 |
Correct |
24 ms |
47288 KB |
Output is correct |
| 30 |
Correct |
357 ms |
108492 KB |
Output is correct |
| 31 |
Correct |
332 ms |
108624 KB |
Output is correct |
| 32 |
Correct |
412 ms |
172988 KB |
Output is correct |
| 33 |
Correct |
380 ms |
204476 KB |
Output is correct |
| 34 |
Correct |
1034 ms |
112252 KB |
Output is correct |
| 35 |
Correct |
1025 ms |
112296 KB |
Output is correct |
| 36 |
Correct |
998 ms |
120076 KB |
Output is correct |
| 37 |
Correct |
1004 ms |
120080 KB |
Output is correct |
| 38 |
Correct |
711 ms |
111752 KB |
Output is correct |
| 39 |
Correct |
683 ms |
111600 KB |
Output is correct |
| 40 |
Correct |
695 ms |
111676 KB |
Output is correct |
