#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#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];
pair <int,int> s[DIMN];
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 == 5)
// printf ("a");
/// maxi[nod] = nr de mutari ale soarecelui ca sa se plimbe in subarborele nod
/// iar apoi sa revina in nod
poz = -1;
maxii = -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){
maxi[nod] = 1;
}
}
int cmp (pair <int,int> a , pair <int,int> b){
if (a.first != b.first)
return a.first > b.first;
return a.second < b.second;
}
int main()
{
FILE *fin = stdin;
FILE *fout = stdout;
int n , m , i , x , y , nod , elem , mustblock , poz , sp ,sol , can , tt , el , p;
int vecin , until;
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);
}
//printf ("%d %d\n",v[t].size() , v[m].size());
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++){
//printf ("%d %d\n",w[i],v[w[i]].size() - 2);
if (w[i] == t)
continue;
mustblock += v[w[i]].size() - 2; /// nici tatal
}
/*for (i=0;i<v[150].size();i++){
int vecin = v[150][i];
if (vecin !=0)
printf ("%d ",maxi[vecin]);
}*/
sol = 0;
nod = m;
can = 0;
tt = 0;
poz = elem;
el = 0;
/*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]){
s[++el] = 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--;
}*/
// for (i=1;i<=el;i++)
// printf ("%d %d %d\n" , s[i].first.first , s[i].first.second , s[i].second);
/* p = 1;
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 && p<=el){
nod = s[p].second;
p++;
while (p<=el && !query(1 ,1 , n , niv[nod])){ /// poti
nod = s[p].second;
p++;
}
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
can = 0;
until = 0;
while (nod != t){
sp = 0;
can++;
tos = 0;
if (v[nod].size() == 2){ /// efectiv nu ai ce sa faci
}
else {
el = 0;
for (i=0;i<v[nod].size();i++){
vecin = v[nod][i];
if (vecin != tt && vecin != w[elem-1]){
s[++el] = make_pair(maxi[vecin] , vecin);
tos++;
/// 1 ca sa cureti drumul vecin , nod dupa ce se blocheaza
/// 1 ca sa blochezi cel mai nasol pasaj
}
}
sort (s + 1 , s + el + 1 , cmp);
for (i=1;i<=el && can;i++){
/// pe asta il blochezi la timp
can--;
until++;
mustblock--;
}
if (!can && i<=el){
sol = maxi[s[i].second] + 1 + mustblock - 1;
fprintf (fout,"%d\n",sol + until);
return 0;
}
}
tt = nod;
nod = w[elem-1];
elem--;
}
//fprintf (fout,"%d",sol + nr);
return 0;
}
Compilation message
mousetrap.cpp: In function 'void dfs(int, int)':
mousetrap.cpp:56:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i=0;i<v[nod].size();i++){
~^~~~~~~~~~~~~~
mousetrap.cpp:70:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i=0;i<v[nod].size();i++){
~^~~~~~~~~~~~~~
mousetrap.cpp:81: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:200:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i=0;i<v[nod].size();i++){
~^~~~~~~~~~~~~~
mousetrap.cpp:110:54: warning: variable 'poz' set but not used [-Wunused-but-set-variable]
int n , m , i , x , y , nod , elem , mustblock , poz , sp ,sol , can , tt , el , p;
^~~
mousetrap.cpp:110:60: warning: variable 'sp' set but not used [-Wunused-but-set-variable]
int n , m , i , x , y , nod , elem , mustblock , poz , sp ,sol , can , tt , el , p;
^~
mousetrap.cpp:110:86: warning: unused variable 'p' [-Wunused-variable]
int n , m , i , x , y , nod , elem , mustblock , poz , sp ,sol , can , tt , el , p;
^
mousetrap.cpp:112: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:114: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 |
Incorrect |
23 ms |
23800 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
479 ms |
78712 KB |
Output is correct |
| 2 |
Correct |
408 ms |
71688 KB |
Output is correct |
| 3 |
Correct |
988 ms |
79224 KB |
Output is correct |
| 4 |
Correct |
470 ms |
52220 KB |
Output is correct |
| 5 |
Correct |
999 ms |
78756 KB |
Output is correct |
| 6 |
Correct |
978 ms |
79240 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
23800 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
23800 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
