#include <cstdio>
#include <vector>
#include <iostream>
#define DIMN 1000010
using namespace std;
int sol;
int fth[DIMN] , w[DIMN] , maxi[DIMN] , t;
vector <int> v[DIMN];
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){
dfs (vecin , nod);
/// cat de in jos te poti duce din nod
}
}
/// 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;
}
}
}
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)
maxi[nod] = min(maxi[nod] , maxi[poz] + 1 + x - 2);
/// pot sa aleg sa nu blochez cel mai nasol pasaj
}
void dfs2 (int nod,int tt,int elem , int mustblock){
int i ,vecin , maxii = 0 , poz , sp;
if (nod == t)
return;
poz = -1;
for (i=0;i<v[nod].size();i++){
vecin = v[nod][i];
if (vecin != tt && vecin != w[elem]){
if (maxii < maxi[vecin]){
maxii = maxi[vecin];
poz = vecin;
}
}
}
sp = 0;
for (i=0;i<v[nod].size();i++){
vecin = v[nod][i];
if (vecin != tt && vecin != poz && vecin != w[elem]){
sp = max (sp , maxi[vecin] + 1 + 1 + mustblock - 1 - 1);
/// 1 ca sa cureti drumul vecin , nod dupa ce se blocheaza
/// 1 ca sa blochezi cel mai nasol pasaj
}
}
if (poz != -1)
sol = max(sol , min(sp , maxi[poz] + 1 + mustblock - 1) );
dfs2 (w[elem] , nod , elem-1 , mustblock - v[nod].size() + 2);
}
int main()
{
FILE *fin = stdin;
FILE *fout = stdout;
int n , m , i , x , y , nod , elem , mustblock;
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;
dfs2 (m , 0 , elem , mustblock);
fprintf (fout,"%d",sol);
return 0;
}
Compilation message
mousetrap.cpp: In function 'void dfs(int, int)':
mousetrap.cpp:12:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i=0;i<v[nod].size();i++){
~^~~~~~~~~~~~~~
mousetrap.cpp:22:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i=0;i<v[nod].size();i++){
~^~~~~~~~~~~~~~
mousetrap.cpp:32:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i=0;i<v[nod].size();i++){
~^~~~~~~~~~~~~~
mousetrap.cpp: In function 'void dfs2(int, int, int, int)':
mousetrap.cpp:51:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i=0;i<v[nod].size();i++){
~^~~~~~~~~~~~~~
mousetrap.cpp:61: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:79: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:81: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 |
481 ms |
74564 KB |
Output is correct |
| 2 |
Correct |
394 ms |
69372 KB |
Output is correct |
| 3 |
Correct |
967 ms |
77668 KB |
Output is correct |
| 4 |
Incorrect |
441 ms |
50552 KB |
Output isn't correct |
| 5 |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
23800 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
