// https://oj.uz/problem/view/CEOI17_mousetrap
#ifndef _GLIBCXX_DEBUG
#define NDEBUG
#endif
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<functional>
#include<cassert>
int nn,trap,mouse;
std::vector<std::vector<int>> ad;
std::vector<int> par; // with root = trap
std::vector<int> nrock; // num of rock to put if mouse is trapped at [?]
// of course the mouse can only be trapped at nodes with <= 1 child (rooted somewhere)
void dfs1(int x){
int const px=par[x];
nrock[x]=nrock[px]+ad[x].size()-2;
for(int child:ad[x])if(child!=px){
par[child]=x;
dfs1(child);
}
}
std::vector<int> d1; // dist(?, line(trap, mouse))
std::vector<int> cost; // total cost if mouse is trapped at [?] = nrock + d1
int thr;
bool dfs3(int x,int par){ // is it possible to force mouse to be trapped at a node with cost <= thr ...
// when start at x?
int nchild=ad[x].size()-(par>=0);
if(nchild==0)return cost[x]<=thr;
if(nchild==1){ // not sure about this, what if deg(mouse) == 1?
if(cost[x]<=thr)return true;
return false; // ???
}
int n_impos=0;
for(int child:ad[x])if(child!=par){
bool ans=dfs3(child,x);
assert(std::cerr<<child<<' '<<x<<" dfs3-> "<<ans<<'\n');
n_impos+=!ans;
}
return n_impos<=1;
}
int main(){
std::ios::sync_with_stdio(false);std::cin.tie(nullptr);
std::cin>>nn>>trap>>mouse;
if(trap==mouse){
std::cout<<"0\n";
return 0;
}
--trap;--mouse;
ad.resize(nn);
for(int u,v,_=nn-1;_--;){
std::cin>>u>>v;--u;--v;
ad[u].push_back(v);
ad[v].push_back(u);
}
nrock.resize(nn);nrock[trap]=1;
par.resize(nn);par[trap]=-1;
for(int x:ad[trap]){
par[x]=trap;
dfs1(x);
}
d1.resize(nn,-1);
std::queue<int> q;
for(int x=mouse;x>=0;x=par[x]){
q.push(x);
d1[x]=0;
}
while(!q.empty()){
int const x=q.front();q.pop();
int const newd=d1[x]+1;assert(newd>0);
for(int y:ad[x])if(d1[y]<0){
d1[y]=newd;
q.push(y);
}
}
cost.resize(nn);
std::transform(begin(nrock),end(nrock),begin(d1),begin(cost),std::plus<int>{});
thr=nn;
for(int r=1<<29;r;r>>=1){
if(thr-r<0)continue;
thr-=r;
if(!dfs3(mouse,-1))
thr+=r;
}
std::cout<<thr<<'\n';
return 0;
}
/*
10 1 4
1 2
2 3
2 4
3 9
3 5
4 7
4 6
6 8
7 10
8 1 2 1 2 1 3 1 4 3 5 3 7 4 6 4 8
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
4 |
Correct |
2 ms |
384 KB |
Output is correct |
5 |
Correct |
2 ms |
384 KB |
Output is correct |
6 |
Correct |
2 ms |
256 KB |
Output is correct |
7 |
Correct |
2 ms |
384 KB |
Output is correct |
8 |
Correct |
2 ms |
256 KB |
Output is correct |
9 |
Correct |
2 ms |
384 KB |
Output is correct |
10 |
Correct |
2 ms |
256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
528 ms |
72804 KB |
Output is correct |
2 |
Correct |
502 ms |
66136 KB |
Output is correct |
3 |
Correct |
2410 ms |
72964 KB |
Output is correct |
4 |
Correct |
1099 ms |
36984 KB |
Output is correct |
5 |
Correct |
2598 ms |
73008 KB |
Output is correct |
6 |
Correct |
2674 ms |
73164 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
4 |
Correct |
2 ms |
384 KB |
Output is correct |
5 |
Correct |
2 ms |
384 KB |
Output is correct |
6 |
Correct |
2 ms |
256 KB |
Output is correct |
7 |
Correct |
2 ms |
384 KB |
Output is correct |
8 |
Correct |
2 ms |
256 KB |
Output is correct |
9 |
Correct |
2 ms |
384 KB |
Output is correct |
10 |
Correct |
2 ms |
256 KB |
Output is correct |
11 |
Correct |
1 ms |
384 KB |
Output is correct |
12 |
Correct |
2 ms |
384 KB |
Output is correct |
13 |
Correct |
2 ms |
384 KB |
Output is correct |
14 |
Correct |
2 ms |
512 KB |
Output is correct |
15 |
Correct |
2 ms |
384 KB |
Output is correct |
16 |
Correct |
3 ms |
384 KB |
Output is correct |
17 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
18 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
4 |
Correct |
2 ms |
384 KB |
Output is correct |
5 |
Correct |
2 ms |
384 KB |
Output is correct |
6 |
Correct |
2 ms |
256 KB |
Output is correct |
7 |
Correct |
2 ms |
384 KB |
Output is correct |
8 |
Correct |
2 ms |
256 KB |
Output is correct |
9 |
Correct |
2 ms |
384 KB |
Output is correct |
10 |
Correct |
2 ms |
256 KB |
Output is correct |
11 |
Correct |
528 ms |
72804 KB |
Output is correct |
12 |
Correct |
502 ms |
66136 KB |
Output is correct |
13 |
Correct |
2410 ms |
72964 KB |
Output is correct |
14 |
Correct |
1099 ms |
36984 KB |
Output is correct |
15 |
Correct |
2598 ms |
73008 KB |
Output is correct |
16 |
Correct |
2674 ms |
73164 KB |
Output is correct |
17 |
Correct |
1 ms |
384 KB |
Output is correct |
18 |
Correct |
2 ms |
384 KB |
Output is correct |
19 |
Correct |
2 ms |
384 KB |
Output is correct |
20 |
Correct |
2 ms |
512 KB |
Output is correct |
21 |
Correct |
2 ms |
384 KB |
Output is correct |
22 |
Correct |
3 ms |
384 KB |
Output is correct |
23 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
24 |
Halted |
0 ms |
0 KB |
- |