#include <iostream>
#include <vector>
#include <bitset>
#include <algorithm>
#define inf 2000000
using namespace std;
vector <int> v[1000001];
bitset <1000001> vis;
int n,m,t,k,nr;
int val_noduri[1000001],fr[1000001],noduri[1000001],vecini[1000001],last_vecini[1000001],p[1000001],dp[1000001];
struct pozitie
{
int val,pos,lazy;
} sol;
struct seg_tree
{
pozitie aint[4000001];
void f (int nod,bool ok)
{
if ((ok&&aint[2*nod].val>=aint[2*nod+1].val)||(!ok&&aint[2*nod].val<=aint[2*nod+1].val))
aint[nod]=aint[2*nod];
else
aint[nod]=aint[2*nod+1];
aint[nod].lazy=0;
}
void build (int nod,int st,int dr,int v[],bool ok)
{
aint[nod].lazy=0;
if (st==dr)
{
aint[nod].val=v[st];
aint[nod].pos=st;
}
else
{
int mij=(st+dr)/2;
build (2*nod,st,mij,v,ok);
build (2*nod+1,mij+1,dr,v,ok);
f (nod,ok);
}
}
void propagate (int nod,int st,int dr)
{
if (st!=dr)
{
aint[2*nod].val+=aint[nod].lazy;
aint[2*nod+1].val+=aint[nod].lazy;
aint[2*nod].lazy+=aint[nod].lazy;
aint[2*nod+1].lazy+=aint[nod].lazy;
}
aint[nod].lazy=0;
}
void update (int nod,int st,int dr,int a,int b,int x,bool ok)
{
if (a>b)
return ;
propagate (nod,st,dr);
if (st>=a&&dr<=b)
{
aint[nod].val+=x;
aint[nod].lazy+=x;
}
else
{
int mij=(st+dr)/2;
if (a<=mij)
update (2*nod,st,mij,a,b,x,ok);
if (b>mij)
update (2*nod+1,mij+1,dr,a,b,x,ok);
f (nod,ok);
}
}
pozitie query ()
{
return aint[1];
}
};
seg_tree aint_noduri,aint_vecini;
void dfs (int nod,int t)
{
p[nod]=t;
for (int i=0; i<v[nod].size (); i++)
{
int vecin=v[nod][i];
if (vecin!=t)
dfs (vecin,nod);
}
}
void dfs_dp (int nod,int t)
{
int max1=0,max2=0,nr=0;
for (int i=0; i<v[nod].size (); i++)
{
int vecin=v[nod][i];
if (vecin==t)
continue;
nr++;
dfs_dp (vecin,nod);
if (dp[vecin]>=max1)
{
max2=max1;
max1=dp[vecin];
}
else if (dp[vecin]>max2)
max2=dp[vecin];
}
dp[nod]=max2+nr;
}
void read ()
{
cin>>n>>t>>m;
int x,y;
for (int i=1; i<n; i++)
{
cin>>x>>y;
v[x].push_back (y);
v[y].push_back (x);
}
}
void get_nodes ()
{
int pos=m;
k=0;
while (pos!=t)
{
k++;
noduri[k]=pos;
val_noduri[k]=k;
vis[pos]=1;
pos=p[pos];
}
vis[t]=1;
reverse (noduri+1,noduri+k+1);
reverse (val_noduri+1,val_noduri+k+1);
aint_noduri.build (1,1,k,val_noduri,0);
}
void get_vecini ()
{
int nrant;
nr=1;
for (int i=1; i<=k; i++)
{
nrant=nr;
for (int j=0; j<v[noduri[i]].size (); j++)
{
int vecin=v[noduri[i]][j];
if (!vis[vecin])
{
dfs_dp (vecin,noduri[i]);
vecini[++nr]=dp[vecin];
fr[nr]=i+1;
}
}
for (int j=nrant+1; j<=nr; j++)
vecini[j]+=nr-1;
last_vecini[i]=nr;
}
aint_vecini.build (1,1,nr,vecini,1);
}
void solve ()
{
int nrvec=min (nr-1,k),minim=1,maxim=0,pos;
while (nrvec>=0&&minim>=0)
{
sol=aint_vecini.query ();
maxim=sol.val;
pos=sol.pos;
if (maxim<0)
{
maxim=0;
break;
}
aint_noduri.update (1,1,k,1,fr[pos],-1,0);
sol=aint_noduri.query ();
minim=sol.val;
if (minim<0)
break;
nrvec--;
aint_vecini.update (1,1,nr,pos,pos,-inf,1);
aint_vecini.update (1,1,nr,1,last_vecini[fr[pos]-1],1,1);
}
cout<<maxim;
}
int main ()
{
read ();
dfs (t,0);
get_nodes ();
get_vecini ();
solve ();
return 0;
}
Compilation message
mousetrap.cpp: In function 'void dfs(int, int)':
mousetrap.cpp:82:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
82 | for (int i=0; i<v[nod].size (); i++)
| ~^~~~~~~~~~~~~~~
mousetrap.cpp: In function 'void dfs_dp(int, int)':
mousetrap.cpp:92:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
92 | for (int i=0; i<v[nod].size (); i++)
| ~^~~~~~~~~~~~~~~
mousetrap.cpp: In function 'void get_vecini()':
mousetrap.cpp:144:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
144 | for (int j=0; j<v[noduri[i]].size (); j++)
| ~^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
23896 KB |
Output is correct |
| 2 |
Correct |
10 ms |
24060 KB |
Output is correct |
| 3 |
Correct |
12 ms |
23932 KB |
Output is correct |
| 4 |
Correct |
11 ms |
23928 KB |
Output is correct |
| 5 |
Correct |
10 ms |
23896 KB |
Output is correct |
| 6 |
Correct |
11 ms |
23896 KB |
Output is correct |
| 7 |
Incorrect |
11 ms |
23900 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
500 ms |
76368 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
23896 KB |
Output is correct |
| 2 |
Correct |
10 ms |
24060 KB |
Output is correct |
| 3 |
Correct |
12 ms |
23932 KB |
Output is correct |
| 4 |
Correct |
11 ms |
23928 KB |
Output is correct |
| 5 |
Correct |
10 ms |
23896 KB |
Output is correct |
| 6 |
Correct |
11 ms |
23896 KB |
Output is correct |
| 7 |
Incorrect |
11 ms |
23900 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
23896 KB |
Output is correct |
| 2 |
Correct |
10 ms |
24060 KB |
Output is correct |
| 3 |
Correct |
12 ms |
23932 KB |
Output is correct |
| 4 |
Correct |
11 ms |
23928 KB |
Output is correct |
| 5 |
Correct |
10 ms |
23896 KB |
Output is correct |
| 6 |
Correct |
11 ms |
23896 KB |
Output is correct |
| 7 |
Incorrect |
11 ms |
23900 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
