//Autor: Bartłomiej Czarkowski
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
template<class A,class B>auto&operator<<(ostream&o,pair<A,B>p){return o<<'('<<p.first<<", "<<p.second<<')';}
template<class T>auto operator<<(ostream&o,T x)->decltype(x.end(),o){o<<'{';int i=0;for(auto e:x)o<<(", ")+2*!i++<<e;return o<<'}';}
#define debug(x...) cerr<<"["#x"]: ",[](auto...$){((cerr<<$<<"; "),...);}(x),cerr<<'\n'
#else
#define debug(...) {}
#endif
const int N = 1001000;
int n, a, b, m, q;
int par[N];
int son[N];
int cost[N];
int blk[N];
int stp[N];
int dp[N]; // ile żeby uwięzić i wyprowadzić do ojca
vector<int> v[N];
void dfs_dp(int x) {
vector<int> war = {0, 0};
for (int i : v[x]) {
if (i == par[x]) {
continue;
}
par[i] = x;
dfs_dp(i);
war.push_back(dp[i]);
}
nth_element(war.begin(), war.begin() + 1, war.end(), [&](int a, int b) {
return a > b;
});
dp[x] = war[1] + war.size() - 2;
}
bool check(int wyn) {
int x = m, nad = 1, usd = 0;
while (x != q) {
int ile = 0;
for (int i : v[x]) {
if (i != par[x] && i != son[x]) {
if (dp[i] + blk[x] + usd > wyn) {
++ile;
}
}
}
if (ile > nad) {
return false;
}
nad -= ile;
usd += ile;
x = par[x];
++nad;
}
return usd <= wyn;
}
int main() {
scanf("%d%d%d", &n, &q, &m);
for (int i = 1; i < n; ++i) {
scanf("%d%d", &a, &b);
v[a].push_back(b);
v[b].push_back(a);
++stp[a];
++stp[b];
}
dfs_dp(q);
int x = m;
while (x != q) {
son[par[x]] = x;
x = par[x];
}
while (x != m) {
x = son[x];
blk[x] = blk[par[x]];
for (int i : v[x]) {
blk[x] += (i != par[x]) && (i != son[x]);
}
}
int bp = -1, bk = max(n, 1000), bs;
while (bk - bp > 1) {
bs = (bp + bk) / 2;
if (check(bs)) {
bk = bs;
}
else {
bp = bs;
}
}
printf("%d\n", bk);
return 0;
}
Compilation message
mousetrap.cpp: In function 'int main()':
mousetrap.cpp:61:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
61 | scanf("%d%d%d", &n, &q, &m);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
mousetrap.cpp:63:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
63 | scanf("%d%d", &a, &b);
| ~~~~~^~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
23764 KB |
Output is correct |
2 |
Correct |
13 ms |
23816 KB |
Output is correct |
3 |
Correct |
15 ms |
23796 KB |
Output is correct |
4 |
Correct |
15 ms |
23840 KB |
Output is correct |
5 |
Correct |
13 ms |
23764 KB |
Output is correct |
6 |
Correct |
12 ms |
23764 KB |
Output is correct |
7 |
Correct |
14 ms |
23776 KB |
Output is correct |
8 |
Correct |
13 ms |
23736 KB |
Output is correct |
9 |
Correct |
13 ms |
23764 KB |
Output is correct |
10 |
Correct |
15 ms |
23748 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
393 ms |
70460 KB |
Output is correct |
2 |
Correct |
357 ms |
65820 KB |
Output is correct |
3 |
Correct |
1008 ms |
71424 KB |
Output is correct |
4 |
Correct |
435 ms |
50256 KB |
Output is correct |
5 |
Correct |
972 ms |
71524 KB |
Output is correct |
6 |
Correct |
975 ms |
71512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
23764 KB |
Output is correct |
2 |
Correct |
13 ms |
23816 KB |
Output is correct |
3 |
Correct |
15 ms |
23796 KB |
Output is correct |
4 |
Correct |
15 ms |
23840 KB |
Output is correct |
5 |
Correct |
13 ms |
23764 KB |
Output is correct |
6 |
Correct |
12 ms |
23764 KB |
Output is correct |
7 |
Correct |
14 ms |
23776 KB |
Output is correct |
8 |
Correct |
13 ms |
23736 KB |
Output is correct |
9 |
Correct |
13 ms |
23764 KB |
Output is correct |
10 |
Correct |
15 ms |
23748 KB |
Output is correct |
11 |
Correct |
13 ms |
23764 KB |
Output is correct |
12 |
Correct |
13 ms |
23868 KB |
Output is correct |
13 |
Correct |
13 ms |
23820 KB |
Output is correct |
14 |
Correct |
12 ms |
23952 KB |
Output is correct |
15 |
Correct |
13 ms |
24020 KB |
Output is correct |
16 |
Correct |
13 ms |
23764 KB |
Output is correct |
17 |
Correct |
14 ms |
23892 KB |
Output is correct |
18 |
Correct |
15 ms |
23824 KB |
Output is correct |
19 |
Correct |
13 ms |
23892 KB |
Output is correct |
20 |
Correct |
13 ms |
23816 KB |
Output is correct |
21 |
Correct |
13 ms |
23828 KB |
Output is correct |
22 |
Correct |
13 ms |
23836 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
23764 KB |
Output is correct |
2 |
Correct |
13 ms |
23816 KB |
Output is correct |
3 |
Correct |
15 ms |
23796 KB |
Output is correct |
4 |
Correct |
15 ms |
23840 KB |
Output is correct |
5 |
Correct |
13 ms |
23764 KB |
Output is correct |
6 |
Correct |
12 ms |
23764 KB |
Output is correct |
7 |
Correct |
14 ms |
23776 KB |
Output is correct |
8 |
Correct |
13 ms |
23736 KB |
Output is correct |
9 |
Correct |
13 ms |
23764 KB |
Output is correct |
10 |
Correct |
15 ms |
23748 KB |
Output is correct |
11 |
Correct |
393 ms |
70460 KB |
Output is correct |
12 |
Correct |
357 ms |
65820 KB |
Output is correct |
13 |
Correct |
1008 ms |
71424 KB |
Output is correct |
14 |
Correct |
435 ms |
50256 KB |
Output is correct |
15 |
Correct |
972 ms |
71524 KB |
Output is correct |
16 |
Correct |
975 ms |
71512 KB |
Output is correct |
17 |
Correct |
13 ms |
23764 KB |
Output is correct |
18 |
Correct |
13 ms |
23868 KB |
Output is correct |
19 |
Correct |
13 ms |
23820 KB |
Output is correct |
20 |
Correct |
12 ms |
23952 KB |
Output is correct |
21 |
Correct |
13 ms |
24020 KB |
Output is correct |
22 |
Correct |
13 ms |
23764 KB |
Output is correct |
23 |
Correct |
14 ms |
23892 KB |
Output is correct |
24 |
Correct |
15 ms |
23824 KB |
Output is correct |
25 |
Correct |
13 ms |
23892 KB |
Output is correct |
26 |
Correct |
13 ms |
23816 KB |
Output is correct |
27 |
Correct |
13 ms |
23828 KB |
Output is correct |
28 |
Correct |
13 ms |
23836 KB |
Output is correct |
29 |
Correct |
13 ms |
23820 KB |
Output is correct |
30 |
Correct |
397 ms |
75640 KB |
Output is correct |
31 |
Correct |
405 ms |
75636 KB |
Output is correct |
32 |
Correct |
571 ms |
224068 KB |
Output is correct |
33 |
Correct |
567 ms |
216204 KB |
Output is correct |
34 |
Correct |
958 ms |
76444 KB |
Output is correct |
35 |
Correct |
973 ms |
76540 KB |
Output is correct |
36 |
Correct |
996 ms |
91156 KB |
Output is correct |
37 |
Correct |
1038 ms |
91308 KB |
Output is correct |
38 |
Correct |
764 ms |
93880 KB |
Output is correct |
39 |
Correct |
778 ms |
88648 KB |
Output is correct |
40 |
Correct |
767 ms |
88748 KB |
Output is correct |