/**
____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|
**/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N_MAX = (int) 1e6;
int N, T, M;
vector <int> adj[N_MAX + 2];
int parent[N_MAX + 2];
int up[N_MAX + 2];
int down[N_MAX + 2];
void dfs (int u) {
int sons = (int) adj[u].size() - (u != T);
int max1 = 0, max2 = 0;
for (int v : adj[u]) {
if (v != parent[u]) {
parent[v] = u;
up[v] = up[u] + (u == T ? 1 : sons);
dfs(v);
if (down[v] >= max1) {
max2 = max1;
max1 = down[v];
} else if (down[v] > max2) {
max2 = down[v];
}
}
}
if (sons == 0) {
down[u] = up[u];
} else if (sons == 1) {
down[u] = up[u] + 1;
} else {
down[u] = max2;
}
}
int path[N_MAX + 2];
int len;
bool check (int answer) {
int block = 0;
for (int i = 1; i <= len; i++) {
int here = 0;
int u = path[i];
for (int v : adj[u]) {
if (v != parent[u] && v != path[i - 1]) {
if (block + down[v] > answer) {
here++;
}
}
}
block += here;
if (block > i) {
return false;
}
}
return (block <= answer);
}
int main () {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> N >> T >> M;
for (int i = 1; i <= N - 1; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
dfs(T);
int u = M;
while (u != T) {
path[++len] = u;
u = parent[u];
}
path[++len] = T;
for (int i = 1; i <= len; i++) {
int u = path[i];
for (int v : adj[u]) {
if (v != parent[u] && v != path[i - 1]) {
down[v] -= (len - i) + (i > 1);
}
}
}
int l = 0, r = N;
while (l < r) {
int mid = (l + r) / 2;
if (check(mid) == true) {
r = mid;
} else {
l = mid + 1;
}
}
cout << l << "\n";
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
23764 KB |
Output is correct |
2 |
Correct |
12 ms |
23764 KB |
Output is correct |
3 |
Correct |
14 ms |
23816 KB |
Output is correct |
4 |
Correct |
12 ms |
23764 KB |
Output is correct |
5 |
Correct |
12 ms |
23840 KB |
Output is correct |
6 |
Correct |
14 ms |
23764 KB |
Output is correct |
7 |
Correct |
13 ms |
23764 KB |
Output is correct |
8 |
Correct |
12 ms |
23768 KB |
Output is correct |
9 |
Correct |
12 ms |
23764 KB |
Output is correct |
10 |
Correct |
13 ms |
23820 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
261 ms |
66832 KB |
Output is correct |
2 |
Correct |
240 ms |
62544 KB |
Output is correct |
3 |
Correct |
632 ms |
67948 KB |
Output is correct |
4 |
Correct |
301 ms |
45820 KB |
Output is correct |
5 |
Correct |
654 ms |
67984 KB |
Output is correct |
6 |
Correct |
632 ms |
67944 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
23764 KB |
Output is correct |
2 |
Correct |
12 ms |
23764 KB |
Output is correct |
3 |
Correct |
14 ms |
23816 KB |
Output is correct |
4 |
Correct |
12 ms |
23764 KB |
Output is correct |
5 |
Correct |
12 ms |
23840 KB |
Output is correct |
6 |
Correct |
14 ms |
23764 KB |
Output is correct |
7 |
Correct |
13 ms |
23764 KB |
Output is correct |
8 |
Correct |
12 ms |
23768 KB |
Output is correct |
9 |
Correct |
12 ms |
23764 KB |
Output is correct |
10 |
Correct |
13 ms |
23820 KB |
Output is correct |
11 |
Correct |
13 ms |
23816 KB |
Output is correct |
12 |
Correct |
13 ms |
23820 KB |
Output is correct |
13 |
Correct |
13 ms |
23772 KB |
Output is correct |
14 |
Correct |
12 ms |
23892 KB |
Output is correct |
15 |
Correct |
12 ms |
23900 KB |
Output is correct |
16 |
Correct |
13 ms |
23888 KB |
Output is correct |
17 |
Correct |
14 ms |
23828 KB |
Output is correct |
18 |
Correct |
13 ms |
23776 KB |
Output is correct |
19 |
Correct |
12 ms |
23892 KB |
Output is correct |
20 |
Correct |
12 ms |
23892 KB |
Output is correct |
21 |
Correct |
13 ms |
23888 KB |
Output is correct |
22 |
Correct |
13 ms |
23796 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
23764 KB |
Output is correct |
2 |
Correct |
12 ms |
23764 KB |
Output is correct |
3 |
Correct |
14 ms |
23816 KB |
Output is correct |
4 |
Correct |
12 ms |
23764 KB |
Output is correct |
5 |
Correct |
12 ms |
23840 KB |
Output is correct |
6 |
Correct |
14 ms |
23764 KB |
Output is correct |
7 |
Correct |
13 ms |
23764 KB |
Output is correct |
8 |
Correct |
12 ms |
23768 KB |
Output is correct |
9 |
Correct |
12 ms |
23764 KB |
Output is correct |
10 |
Correct |
13 ms |
23820 KB |
Output is correct |
11 |
Correct |
261 ms |
66832 KB |
Output is correct |
12 |
Correct |
240 ms |
62544 KB |
Output is correct |
13 |
Correct |
632 ms |
67948 KB |
Output is correct |
14 |
Correct |
301 ms |
45820 KB |
Output is correct |
15 |
Correct |
654 ms |
67984 KB |
Output is correct |
16 |
Correct |
632 ms |
67944 KB |
Output is correct |
17 |
Correct |
13 ms |
23816 KB |
Output is correct |
18 |
Correct |
13 ms |
23820 KB |
Output is correct |
19 |
Correct |
13 ms |
23772 KB |
Output is correct |
20 |
Correct |
12 ms |
23892 KB |
Output is correct |
21 |
Correct |
12 ms |
23900 KB |
Output is correct |
22 |
Correct |
13 ms |
23888 KB |
Output is correct |
23 |
Correct |
14 ms |
23828 KB |
Output is correct |
24 |
Correct |
13 ms |
23776 KB |
Output is correct |
25 |
Correct |
12 ms |
23892 KB |
Output is correct |
26 |
Correct |
12 ms |
23892 KB |
Output is correct |
27 |
Correct |
13 ms |
23888 KB |
Output is correct |
28 |
Correct |
13 ms |
23796 KB |
Output is correct |
29 |
Correct |
13 ms |
23724 KB |
Output is correct |
30 |
Correct |
273 ms |
80196 KB |
Output is correct |
31 |
Correct |
277 ms |
80184 KB |
Output is correct |
32 |
Correct |
394 ms |
178320 KB |
Output is correct |
33 |
Correct |
307 ms |
174216 KB |
Output is correct |
34 |
Correct |
657 ms |
81184 KB |
Output is correct |
35 |
Correct |
665 ms |
81324 KB |
Output is correct |
36 |
Correct |
697 ms |
90956 KB |
Output is correct |
37 |
Correct |
699 ms |
90788 KB |
Output is correct |
38 |
Correct |
488 ms |
93644 KB |
Output is correct |
39 |
Correct |
512 ms |
93816 KB |
Output is correct |
40 |
Correct |
488 ms |
93620 KB |
Output is correct |