/******************************************************************************
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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
47316 KB |
Output is correct |
| 2 |
Correct |
22 ms |
47316 KB |
Output is correct |
| 3 |
Correct |
24 ms |
47288 KB |
Output is correct |
| 4 |
Correct |
21 ms |
47316 KB |
Output is correct |
| 5 |
Correct |
22 ms |
47268 KB |
Output is correct |
| 6 |
Correct |
22 ms |
47288 KB |
Output is correct |
| 7 |
Correct |
23 ms |
47216 KB |
Output is correct |
| 8 |
Correct |
22 ms |
47192 KB |
Output is correct |
| 9 |
Correct |
23 ms |
47256 KB |
Output is correct |
| 10 |
Correct |
22 ms |
47292 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
335 ms |
108044 KB |
Output is correct |
| 2 |
Correct |
315 ms |
113864 KB |
Output is correct |
| 3 |
Correct |
986 ms |
124748 KB |
Output is correct |
| 4 |
Correct |
442 ms |
85992 KB |
Output is correct |
| 5 |
Correct |
969 ms |
124748 KB |
Output is correct |
| 6 |
Correct |
968 ms |
124856 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
47316 KB |
Output is correct |
| 2 |
Correct |
22 ms |
47316 KB |
Output is correct |
| 3 |
Correct |
24 ms |
47288 KB |
Output is correct |
| 4 |
Correct |
21 ms |
47316 KB |
Output is correct |
| 5 |
Correct |
22 ms |
47268 KB |
Output is correct |
| 6 |
Correct |
22 ms |
47288 KB |
Output is correct |
| 7 |
Correct |
23 ms |
47216 KB |
Output is correct |
| 8 |
Correct |
22 ms |
47192 KB |
Output is correct |
| 9 |
Correct |
23 ms |
47256 KB |
Output is correct |
| 10 |
Correct |
22 ms |
47292 KB |
Output is correct |
| 11 |
Correct |
22 ms |
47220 KB |
Output is correct |
| 12 |
Correct |
22 ms |
47312 KB |
Output is correct |
| 13 |
Correct |
22 ms |
47316 KB |
Output is correct |
| 14 |
Correct |
24 ms |
47444 KB |
Output is correct |
| 15 |
Correct |
24 ms |
47308 KB |
Output is correct |
| 16 |
Correct |
22 ms |
47280 KB |
Output is correct |
| 17 |
Correct |
24 ms |
47316 KB |
Output is correct |
| 18 |
Correct |
23 ms |
47292 KB |
Output is correct |
| 19 |
Correct |
22 ms |
47388 KB |
Output is correct |
| 20 |
Correct |
22 ms |
47344 KB |
Output is correct |
| 21 |
Correct |
22 ms |
47280 KB |
Output is correct |
| 22 |
Correct |
22 ms |
47368 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
47316 KB |
Output is correct |
| 2 |
Correct |
22 ms |
47316 KB |
Output is correct |
| 3 |
Correct |
24 ms |
47288 KB |
Output is correct |
| 4 |
Correct |
21 ms |
47316 KB |
Output is correct |
| 5 |
Correct |
22 ms |
47268 KB |
Output is correct |
| 6 |
Correct |
22 ms |
47288 KB |
Output is correct |
| 7 |
Correct |
23 ms |
47216 KB |
Output is correct |
| 8 |
Correct |
22 ms |
47192 KB |
Output is correct |
| 9 |
Correct |
23 ms |
47256 KB |
Output is correct |
| 10 |
Correct |
22 ms |
47292 KB |
Output is correct |
| 11 |
Correct |
335 ms |
108044 KB |
Output is correct |
| 12 |
Correct |
315 ms |
113864 KB |
Output is correct |
| 13 |
Correct |
986 ms |
124748 KB |
Output is correct |
| 14 |
Correct |
442 ms |
85992 KB |
Output is correct |
| 15 |
Correct |
969 ms |
124748 KB |
Output is correct |
| 16 |
Correct |
968 ms |
124856 KB |
Output is correct |
| 17 |
Correct |
22 ms |
47220 KB |
Output is correct |
| 18 |
Correct |
22 ms |
47312 KB |
Output is correct |
| 19 |
Correct |
22 ms |
47316 KB |
Output is correct |
| 20 |
Correct |
24 ms |
47444 KB |
Output is correct |
| 21 |
Correct |
24 ms |
47308 KB |
Output is correct |
| 22 |
Correct |
22 ms |
47280 KB |
Output is correct |
| 23 |
Correct |
24 ms |
47316 KB |
Output is correct |
| 24 |
Correct |
23 ms |
47292 KB |
Output is correct |
| 25 |
Correct |
22 ms |
47388 KB |
Output is correct |
| 26 |
Correct |
22 ms |
47344 KB |
Output is correct |
| 27 |
Correct |
22 ms |
47280 KB |
Output is correct |
| 28 |
Correct |
22 ms |
47368 KB |
Output is correct |
| 29 |
Correct |
21 ms |
47288 KB |
Output is correct |
| 30 |
Correct |
350 ms |
121332 KB |
Output is correct |
| 31 |
Correct |
337 ms |
121280 KB |
Output is correct |
| 32 |
Correct |
385 ms |
186036 KB |
Output is correct |
| 33 |
Correct |
390 ms |
217292 KB |
Output is correct |
| 34 |
Correct |
999 ms |
124736 KB |
Output is correct |
| 35 |
Correct |
989 ms |
124860 KB |
Output is correct |
| 36 |
Correct |
985 ms |
132448 KB |
Output is correct |
| 37 |
Correct |
974 ms |
132364 KB |
Output is correct |
| 38 |
Correct |
695 ms |
124344 KB |
Output is correct |
| 39 |
Correct |
679 ms |
124176 KB |
Output is correct |
| 40 |
Correct |
696 ms |
124232 KB |
Output is correct |
