#include <bits/stdc++.h>
#define forn(i,j,n) for(ll i = (ll)j;i<=(ll)n;i++)
#define nfor(i,j,n) for(ll i = (ll)j;i>=(ll)n;i--)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
const ll N = 2000001,LOG = 17;
ll n,t,m,dep[N],d[N],src;
vector<pair<ll,pii> > g[N];
ll dfs1(ll u,ll prnt,ll depth){
dep[u] = depth;
d[u] = depth;
ll ret = 0;
forn(i,0,g[u].size() - 1){
ll v = g[u][i].second.second;
if(v == prnt)
continue;
ll tmp = dfs1(v,u,depth+1);
ret = max(ret,tmp);
dep[u] = max(dep[u],dep[v]);
g[u][i].first = tmp;
g[u][i].second.first = -dep[v];
}
if(u == t)
return 1;
return ret;
}
void fix(ll &id,ll &one,ll &two,ll &node,ll &prnt){
while(one <= two && id < g[node].size() && g[node][id].first != 1){
if(g[node][id].second.second != prnt && g[node][id].first != -1)
one++;
g[node][id].first = -1;
id++;
}
while(id < g[node].size() && g[node][id].first == -1)
++id;
}
void dfs(ll node,ll prnt,ll &one,ll &two,ll in){
if(node == t)
return;
ll id = 0;
fix(id,one,two,node,prnt);
while(id < g[node].size()){
fix(id,one,two,node,prnt);
if(g[node][id].second.second == prnt || g[node][id].first == -1){
id++;
continue;
}
if(g[node][id].first == 0){
dfs(g[node][id].second.second,node,one,++two,2);
g[node][id].first = -1;
one++;
two++;
}else{
dfs(g[node][id].second.second,node,one,++two,1);
return;
}
}
}
int main(){
scanf("%lld%lld%lld",&n,&t,&m);
forn(i,1,n-1){
ll u,v;
scanf("%lld%lld",&u,&v);
g[u].push_back(make_pair(0,make_pair(0,v)));
g[v].push_back(make_pair(0,make_pair(0,u)));
}
dfs1(m,0,0);
forn(i,1,n){
sort(g[i].begin(),g[i].end());
// forn(j,0,g[i].size()-1){
// cout<<g[i][j].first<<" "<<g[i][j].second.first<<" "<<g[i][j].second.second<<endl;
// }
// cout<<endl;
}
ll one = 0,two = 0;
dfs(m,0,one,two,1);
cout<<one;
return 0;
}
Compilation message
mousetrap.cpp: In function 'void fix(ll&, ll&, ll&, ll&, ll&)':
mousetrap.cpp:31:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(one <= two && id < g[node].size() && g[node][id].first != 1){
~~~^~~~~~~~~~~~~~~~
mousetrap.cpp:37:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(id < g[node].size() && g[node][id].first == -1)
~~~^~~~~~~~~~~~~~~~
mousetrap.cpp: In function 'void dfs(ll, ll, ll&, ll&, ll)':
mousetrap.cpp:45:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(id < g[node].size()){
~~~^~~~~~~~~~~~~~~~
mousetrap.cpp: In function 'int main()':
mousetrap.cpp:64:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld%lld",&n,&t,&m);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
mousetrap.cpp:67:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld",&u,&v);
~~~~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
44 ms |
47352 KB |
Output is correct |
| 2 |
Correct |
51 ms |
47448 KB |
Output is correct |
| 3 |
Correct |
43 ms |
47448 KB |
Output is correct |
| 4 |
Correct |
45 ms |
47448 KB |
Output is correct |
| 5 |
Correct |
52 ms |
47448 KB |
Output is correct |
| 6 |
Correct |
50 ms |
47548 KB |
Output is correct |
| 7 |
Incorrect |
43 ms |
47548 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
611 ms |
133588 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
44 ms |
47352 KB |
Output is correct |
| 2 |
Correct |
51 ms |
47448 KB |
Output is correct |
| 3 |
Correct |
43 ms |
47448 KB |
Output is correct |
| 4 |
Correct |
45 ms |
47448 KB |
Output is correct |
| 5 |
Correct |
52 ms |
47448 KB |
Output is correct |
| 6 |
Correct |
50 ms |
47548 KB |
Output is correct |
| 7 |
Incorrect |
43 ms |
47548 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
44 ms |
47352 KB |
Output is correct |
| 2 |
Correct |
51 ms |
47448 KB |
Output is correct |
| 3 |
Correct |
43 ms |
47448 KB |
Output is correct |
| 4 |
Correct |
45 ms |
47448 KB |
Output is correct |
| 5 |
Correct |
52 ms |
47448 KB |
Output is correct |
| 6 |
Correct |
50 ms |
47548 KB |
Output is correct |
| 7 |
Incorrect |
43 ms |
47548 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
