#include <bits/stdc++.h>
using namespace std;
int n, a, b;
vector < int > g [300010];
int l [300010];
int dp [300010];
vector <int> pom;
int mark_path (int x, int par){
if (x==a) return l [x]=0;
int ret=-1;
for (int i=0; i<g [x].size(); i++){
int y=g [x][i];
if (y==par) continue;
int val=mark_path (y, x);
if (val!=-1) ret=val+1;
}
return l [x]=ret;
}
int rek (int x, int mid, int par, int od, int sus){
vector <int> my; my.clear ();
for (int i=0; i<g [x].size(); i++){
int y=g [x][i];
if (y==par) continue;
if (sus && l [y]!=-1) continue;
if (l [y]==mid){
if (od && dp [y]==-1) my.push_back (rek (y, mid, x, od, 1));
continue;
}
if (l [x]==mid){
if (l [y]==mid+1 || (l [y]==mid-1 && mid-1!=-1)){
continue;
}
}
my.push_back (rek (y, mid, x, od, sus));
}
sort (my.begin(), my.end()); reverse (my.begin(), my.end());
int sol=0;
for (int i=0; i<my.size(); i++) sol=max (sol, my [i]+(i+1));
return dp [x]=sol;
}
int main(){
memset (l, -1, sizeof l);
cin >> n >> a >> b;
for (int i=0; i<n-1; i++){
int x, y; cin >> x >> y;
g [x].push_back (y);
g [y].push_back (x);
}
mark_path (b, -1);
/*cout << "Prosao: " << endl;
for (int i=1; i<n+1; i++) cout << l [i] << " ";
cout << endl;*/
int lo=0; int hi=l [b];
while (lo!=hi){
int mid=(lo+hi)/2;
memset (dp, -1, sizeof dp); int sol1=rek (a, mid, -1, 0, 0);
int sol2=rek (b, mid, -1, 1, 0);
if (sol1<sol2) lo=mid+1;
else hi=mid;
//cout << lo << " " << hi << endl;
}
memset (dp, -1, sizeof dp); int sol1=rek (a, lo, -1, 0, 0);
int sol2=rek (b, lo, -1, 1, 0);
memset (dp, -1, sizeof dp); int sol4=rek (a, lo-1, -1, 0, 0);
int sol5=rek (b, lo-1, -1, 1, 0);
//cout << lo << " " << sol1 << " " << sol2 << " " << sol3 << endl;
cout << min (max (sol1, sol2), max (sol4, sol5)) << endl;
}
Compilation message
torrent.cpp: In function 'int mark_path(int, int)':
torrent.cpp:11:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
11 | for (int i=0; i<g [x].size(); i++){
| ~^~~~~~~~~~~~~
torrent.cpp: In function 'int rek(int, int, int, int, int)':
torrent.cpp:21:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
21 | for (int i=0; i<g [x].size(); i++){
| ~^~~~~~~~~~~~~
torrent.cpp:38:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
38 | for (int i=0; i<my.size(); i++) sol=max (sol, my [i]+(i+1));
| ~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
9628 KB |
Output is correct |
| 2 |
Correct |
6 ms |
9688 KB |
Output is correct |
| 3 |
Correct |
7 ms |
9680 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
532 ms |
24004 KB |
Output is correct |
| 2 |
Correct |
559 ms |
28112 KB |
Output is correct |
| 3 |
Correct |
518 ms |
28784 KB |
Output is correct |
| 4 |
Correct |
631 ms |
29420 KB |
Output is correct |
| 5 |
Correct |
573 ms |
25736 KB |
Output is correct |
| 6 |
Correct |
496 ms |
25908 KB |
Output is correct |
| 7 |
Correct |
495 ms |
29476 KB |
Output is correct |
