#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n, S, T;
vector <int> g[N];
int f[N], flag[N];
void dfs(int u, int p) {
int best[3] = {0, 0, 0};
for (auto v: g[u]) {
if (v == p) continue;
dfs(v, u);
best[2] = f[v];
sort(best, best + 3);
reverse(best, best + 3);
}
f[u] = best[1] + g[u].size() - 1;
}
int par[N];
void init(int u, int p) {
par[u] = p;
for (auto v: g[u]) {
if (v == p) continue;
init(v, u);
}
}
vector <int> s[N];
int main() {
// freopen("mousetrap.inp", "r", stdin);
ios :: sync_with_stdio(0); cin.tie(0);
cin >> n >> T >> S;
for (int i = 1; i < n; ++i) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
init(S, 0);
vector <int> path;
for (int u = T; u != S; u = par[u]) flag[par[u]] = 1, path.push_back(par[u]);
reverse(path.begin(), path.end());
int need = 0;
for (auto u: path) {
for (auto v: g[u]) {
if (flag[v]) continue;
if (v == T) continue;
++need;
dfs(v, u);
s[u].push_back(f[v]);
}
}
for (int u = 1; u <= n; ++u) {
sort(s[u].begin(), s[u].end());
reverse(s[u].begin(), s[u].end());
}
auto check = [&](int limit) {
int k = 0, tot = 0;
for (auto u: path) {
++k;
int i = 0;
while (i < s[u].size() && s[u][i] + need > limit) {
--k;
if (k < 0) return 0;
++tot;
++i;
}
}
if (tot > limit) return 0;
return 1;
};
int L = need, R = n;
while (L < R) {
int mid = L + R >> 1;
if (check(mid)) R = mid;
else L = mid + 1;
}
cout << L;
}
Compilation message
mousetrap.cpp: In lambda function:
mousetrap.cpp:68:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
68 | while (i < s[u].size() && s[u][i] + need > limit) {
| ~~^~~~~~~~~~~~~
mousetrap.cpp: In function 'int main()':
mousetrap.cpp:80:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
80 | int mid = L + R >> 1;
| ~~^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
47188 KB |
Output is correct |
2 |
Correct |
23 ms |
47188 KB |
Output is correct |
3 |
Correct |
23 ms |
47180 KB |
Output is correct |
4 |
Correct |
23 ms |
47272 KB |
Output is correct |
5 |
Correct |
24 ms |
47220 KB |
Output is correct |
6 |
Correct |
23 ms |
47308 KB |
Output is correct |
7 |
Correct |
22 ms |
47188 KB |
Output is correct |
8 |
Correct |
22 ms |
47188 KB |
Output is correct |
9 |
Correct |
25 ms |
47180 KB |
Output is correct |
10 |
Correct |
22 ms |
47244 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
286 ms |
86360 KB |
Output is correct |
2 |
Correct |
271 ms |
82548 KB |
Output is correct |
3 |
Correct |
781 ms |
87516 KB |
Output is correct |
4 |
Correct |
381 ms |
67416 KB |
Output is correct |
5 |
Correct |
792 ms |
87444 KB |
Output is correct |
6 |
Correct |
792 ms |
87592 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
47188 KB |
Output is correct |
2 |
Correct |
23 ms |
47188 KB |
Output is correct |
3 |
Correct |
23 ms |
47180 KB |
Output is correct |
4 |
Correct |
23 ms |
47272 KB |
Output is correct |
5 |
Correct |
24 ms |
47220 KB |
Output is correct |
6 |
Correct |
23 ms |
47308 KB |
Output is correct |
7 |
Correct |
22 ms |
47188 KB |
Output is correct |
8 |
Correct |
22 ms |
47188 KB |
Output is correct |
9 |
Correct |
25 ms |
47180 KB |
Output is correct |
10 |
Correct |
22 ms |
47244 KB |
Output is correct |
11 |
Correct |
22 ms |
47180 KB |
Output is correct |
12 |
Correct |
22 ms |
47316 KB |
Output is correct |
13 |
Correct |
22 ms |
47316 KB |
Output is correct |
14 |
Correct |
24 ms |
47372 KB |
Output is correct |
15 |
Correct |
29 ms |
47260 KB |
Output is correct |
16 |
Incorrect |
23 ms |
47444 KB |
Output isn't correct |
17 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
47188 KB |
Output is correct |
2 |
Correct |
23 ms |
47188 KB |
Output is correct |
3 |
Correct |
23 ms |
47180 KB |
Output is correct |
4 |
Correct |
23 ms |
47272 KB |
Output is correct |
5 |
Correct |
24 ms |
47220 KB |
Output is correct |
6 |
Correct |
23 ms |
47308 KB |
Output is correct |
7 |
Correct |
22 ms |
47188 KB |
Output is correct |
8 |
Correct |
22 ms |
47188 KB |
Output is correct |
9 |
Correct |
25 ms |
47180 KB |
Output is correct |
10 |
Correct |
22 ms |
47244 KB |
Output is correct |
11 |
Correct |
286 ms |
86360 KB |
Output is correct |
12 |
Correct |
271 ms |
82548 KB |
Output is correct |
13 |
Correct |
781 ms |
87516 KB |
Output is correct |
14 |
Correct |
381 ms |
67416 KB |
Output is correct |
15 |
Correct |
792 ms |
87444 KB |
Output is correct |
16 |
Correct |
792 ms |
87592 KB |
Output is correct |
17 |
Correct |
22 ms |
47180 KB |
Output is correct |
18 |
Correct |
22 ms |
47316 KB |
Output is correct |
19 |
Correct |
22 ms |
47316 KB |
Output is correct |
20 |
Correct |
24 ms |
47372 KB |
Output is correct |
21 |
Correct |
29 ms |
47260 KB |
Output is correct |
22 |
Incorrect |
23 ms |
47444 KB |
Output isn't correct |
23 |
Halted |
0 ms |
0 KB |
- |