#include <cstdio>
#include <vector>
#include <iostream>
#include <queue>
#define DIMN 1000010
using namespace std;
int fth[DIMN] , w[DIMN] , maxi[DIMN] , t , blocked[DIMN] , niv[DIMN];
int aib[DIMN];
pair <int,int> aint[4*DIMN];
vector <int> v[DIMN];
priority_queue <pair <pair <int,int>,int> > h;
FILE *fin = stdin;
FILE *fout = stdout;
inline void lazy_update (int nod,int st,int dr){
if (!aint[nod].second) /// nu ii trb lazy
return;
if (st<dr){ /// nu e frunza
aint[2*nod].second+=aint[nod].second; /// pass lazy
aint[2*nod+1].second+=aint[nod].second;
}
aint[nod].first+=aint[nod].second;
aint[nod].second=0;
}
int query (int nod , int st ,int dr , int poz){
int mid = ( st + dr )/2 , x;
lazy_update(nod , st , dr);
if (st == dr)
return aint[nod].first;
if (poz<=mid)
x = query (2*nod,st,mid,poz);
else
x = query (2*nod+1,mid+1,dr,poz);
lazy_update (2*nod,st,mid);
lazy_update (2*nod+1,mid+1,dr);
return x;
}
void update_interv (int nod,int st,int dr,int l,int r,int add){
int mid=(st+dr)/2;
lazy_update (nod,st,dr);
if (l<=st && dr<=r){
aint[nod].second+=add; /// nu ma mai duc in jos
lazy_update (nod,st,dr);
return;
}
if (l<=mid)
update_interv (2*nod,st,mid,l,r,add);
if (mid+1<=r)
update_interv (2*nod+1,mid+1,dr,l,r,add);
lazy_update (2*nod,st,mid);
lazy_update (2*nod+1,mid+1,dr);
}
void dfs (int nod,int tt){
int i , vecin , maxii = 0 , poz;
fth[nod] = tt;
for (i=0;i<v[nod].size();i++){
vecin = v[nod][i];
if (vecin != tt){
niv[vecin] = 1 + niv[nod];
dfs (vecin , nod);
/// cat de in jos te poti duce din nod
}
}
//if (nod == 256)
// printf ("a");
/// maxi[nod] = nr de mutari ale soarecelui ca sa se plimbe in subarborele nod
/// iar apoi sa revina in nod
poz = -1;
for (i=0;i<v[nod].size();i++){
vecin = v[nod][i];
if (vecin != tt){
if (maxii < maxi[vecin]){
maxii = maxi[vecin];
poz = vecin;
}
}
}
maxi[nod] = -1;
int x = v[nod].size();
for (i=0;i<v[nod].size();i++){
vecin = v[nod][i];
if (vecin != tt && vecin != poz){
maxi[nod] = max (maxi[nod] , maxi[vecin] + 1 + 1 + x - 3);
/// 1 ca sa cureti drumul vecin , nod dupa ce se blocheaza
/// 1 ca sa blochezi cel mai nasol pasaj
}
}
if (poz != -1){
if (maxi[nod] == -1)
maxi[nod] = maxi[poz] + 1 + x - 2;
maxi[nod] = min(maxi[nod] , maxi[poz] + 1 + x - 2);
}
else maxi[nod] = 0;
/// pot sa aleg sa nu blochez cel mai nasol pasaj
if (v[nod].size() == 2){
// printf ("%d %d\n",nod,maxi[nod]);
maxi[nod] = 1;
}
}
int main()
{
int n , m , i , x , y , nod , elem , mustblock , poz , sp ,sol , can , tt;
int vecin;
fscanf (fin,"%d%d%d",&n,&t,&m);
for (i=1;i<n;i++){
fscanf (fin,"%d%d",&x,&y);
v[x].push_back(y);
v[y].push_back(x);
}
v[m].push_back(0);
dfs (m , 0);
/// practic soarecele isi alege un singur subarbore in care se duce cat vrea el
/// apio cand se blocheaza
nod = t;
elem = 0;
w[++elem] = t;
while (fth[nod]){
w[++elem] = fth[nod];
nod = fth[nod];
}
mustblock = 0;
for (i=1;i<=elem;i++){
if (w[i] == t)
continue;
mustblock += v[w[i]].size() - 2; /// nici tatal
}
sol = 0;
nod = m;
can = 0;
tt = 0;
poz = elem;
while (nod != t){
//printf ("%d ", nod);
for (i=0;i<v[nod].size();i++){
vecin = v[nod][i];
if (vecin != tt && vecin != w[poz-1]){
h.push(make_pair(make_pair(maxi[vecin] , -niv[vecin]) , vecin));
/// astia sunt vecinii pe care poti tu sa ii blochezi
}
}
tt = nod;
nod = w[poz-1];
poz--;
}
can = niv[t];
for (i=1;i<=niv[t];i++)
update_interv (1 , 1 , n , i , i , i);
/// o sa tin niv de la 1
int nr = 0;
while (can && !h.empty()){
nod = h.top().second;
h.pop();
while (!h.empty() && !query(1 ,1 , n , niv[nod])){ /// poti
nod = h.top().second;
h.pop();
}
if (!query(1 ,1 , n , niv[nod]))
break;
update_interv (1 , 1 , n , niv[nod] , n , -1);
blocked[nod] = 1;
nr++;
can--;
}
nod = m;
tt = 0;
int tos = 0;
/// poti sa blochezi can pasaje in drumul
while (nod != t){
sp = 0;
tos = 0;
for (i=0;i<v[nod].size();i++){
vecin = v[nod][i];
if (vecin != tt && !blocked[vecin] && vecin != w[elem-1]){
sp = max (sp , maxi[vecin] + 1 + 1 + mustblock - nr - 1 - 1);
tos++;
/// 1 ca sa cureti drumul vecin , nod dupa ce se blocheaza
/// 1 ca sa blochezi cel mai nasol pasaj
}
}
sol = max (sol , sp);
tt = nod;
mustblock -= tos;
nod = w[elem-1];
elem--;
}
fprintf (fout,"%d",sol + nr);
return 0;
}
Compilation message
mousetrap.cpp: In function 'void dfs(int, int)':
mousetrap.cpp:58:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i=0;i<v[nod].size();i++){
~^~~~~~~~~~~~~~
mousetrap.cpp:71:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i=0;i<v[nod].size();i++){
~^~~~~~~~~~~~~~
mousetrap.cpp:82:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i=0;i<v[nod].size();i++){
~^~~~~~~~~~~~~~
mousetrap.cpp: In function 'int main()':
mousetrap.cpp:136:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i=0;i<v[nod].size();i++){
~^~~~~~~~~~~~~~
mousetrap.cpp:174:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i=0;i<v[nod].size();i++){
~^~~~~~~~~~~~~~
mousetrap.cpp:106:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
fscanf (fin,"%d%d%d",&n,&t,&m);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
mousetrap.cpp:108:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
fscanf (fin,"%d%d",&x,&y);
~~~~~~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
23800 KB |
Output is correct |
| 2 |
Correct |
23 ms |
23800 KB |
Output is correct |
| 3 |
Correct |
24 ms |
23800 KB |
Output is correct |
| 4 |
Correct |
23 ms |
23928 KB |
Output is correct |
| 5 |
Correct |
23 ms |
23928 KB |
Output is correct |
| 6 |
Correct |
23 ms |
23800 KB |
Output is correct |
| 7 |
Incorrect |
23 ms |
23928 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
442 ms |
67236 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
23800 KB |
Output is correct |
| 2 |
Correct |
23 ms |
23800 KB |
Output is correct |
| 3 |
Correct |
24 ms |
23800 KB |
Output is correct |
| 4 |
Correct |
23 ms |
23928 KB |
Output is correct |
| 5 |
Correct |
23 ms |
23928 KB |
Output is correct |
| 6 |
Correct |
23 ms |
23800 KB |
Output is correct |
| 7 |
Incorrect |
23 ms |
23928 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
23800 KB |
Output is correct |
| 2 |
Correct |
23 ms |
23800 KB |
Output is correct |
| 3 |
Correct |
24 ms |
23800 KB |
Output is correct |
| 4 |
Correct |
23 ms |
23928 KB |
Output is correct |
| 5 |
Correct |
23 ms |
23928 KB |
Output is correct |
| 6 |
Correct |
23 ms |
23800 KB |
Output is correct |
| 7 |
Incorrect |
23 ms |
23928 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
