This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
int n, a, b;
vector < int > g [200010];
int l [200010];
int dp [200010];
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);
memset (dp, -1, sizeof dp); int sol3=rek (a, mid+1, -1, 0, 0);
int sol4=rek (b, mid+1, -1, 1, 0);
if (max (sol1, sol2)==max (sol3, sol4)){
lo=mid; break;
}
if (max (sol1, sol2)<max (sol3, sol4)) hi=mid;
else lo=mid+1;
//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);
//cout << lo << " " << sol1 << " " << sol2 << endl;
cout << max (sol1, sol2) << endl;
}
Compilation message (stderr)
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 |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |