#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<cstring>
using namespace std;
int a,b,n,mid;
vector<int> sus[300500];
int par[300500];
int kolsus[300500];
int vrijeme[300500];
vector<pair<int,int> >v1;
vector<pair<int,int> >edgevi;
pair<int,int>makni;
void input(){
cin>>n>>a>>b;
int br1,br2;
for(int i=0;i<n-1;i++){
cin>>br1>>br2;
sus[br1].push_back(br2);
sus[br2].push_back(br1);
kolsus[br1]++;
kolsus[br2]++;
}
}
void dfs1(int node, int caca){
par[node]=caca;
for(int i=0;i<sus[node].size();i++){
int x=sus[node][i];
if(x==caca)continue;
if((x==edgevi[mid].first && node==edgevi[mid].second) || (node==edgevi[mid].first && x==edgevi[mid].second))continue;
dfs1(x, node);
}
}
int dfs2(int node, int caca){
if(sus[node].size()==1 && node!=a && node!=b)return 1;
vector<int>v;
for(int i=0;i<sus[node].size();i++){
int x=sus[node][i];
if(x==caca)continue;
if((x==edgevi[mid].first && node==edgevi[mid].second) || (node==edgevi[mid].first && x==edgevi[mid].second))continue;
//vrijeme[node]=max(vrijeme[node], dfs2(x, node));
v.push_back(dfs2(x, node));
}
if(v.empty())
return 1;
sort(v.rbegin(),v.rend());
int maxx=v[0];
for(int i=1;i<v.size();i++){
if(v[i]+i>maxx)maxx=v[i]+i;
}
vrijeme[node]=maxx;
//int raz=(sus[node].size()-1)-vrijeme[node];
//if(raz>0)vrijeme[node]+=raz;
//return vrijeme[node]+1;
return maxx+1;
}
void dfs3(int node, int caca){
if(node==b && edgevi.size()==0){
for(int i=0;i<v1.size();i++)edgevi.push_back(v1[i]);
}
for(int i=0;i<sus[node].size();i++){
int x=sus[node][i];
if(x==caca)continue;
v1.push_back(make_pair(node,x));
dfs3(x,node);
v1.pop_back();
}
}
int binary(){
int lo=0;
int hi=edgevi.size()-1;
while(lo<hi){
mid=(lo+hi)/2;
dfs1(a,a);
dfs1(b,b);
//for(int i=1;i<=n;i++)cout<<i<<" "<<par[i]<<endl;
//cout<<endl<<endl;
dfs2(a,a);
int av=vrijeme[a];
dfs2(b,b);
int bv=vrijeme[b];
//cout<<endl<<endl;
//for(int i=1;i<=n;i++)cout<<i<<" "<<vrijeme[i]<<endl;
//cout<<endl<<endl;
//cout<<mid<<" "<<av<<" "<<bv<<endl;
if(av>bv)hi=mid;
else lo=mid+1;
}
int av=0,bv=0;
mid=lo;
if(mid<edgevi.size()){
mid=lo;
dfs1(a,a);
dfs2(a,a);
av=vrijeme[a];
}
if(mid!=0){
mid--;
dfs1(b,b);
dfs2(b,b);
bv=vrijeme[b];
}
//for(int i=1;i<n;i++)cout<<i<<" "<<vrijeme[i]<<endl;
return min(av,bv);
}
void solve(){
//cout<<endl;
//dfs1(a,a);
/*for(int i=1;i<=n;i++){
cout<<i<<" -> ";
for(int j=0;j<sus[i].size();j++){
cout<<sus[i][j]<<" ";
}
cout<<endl;
}*/
dfs3(a,a);
//for(int i=0;i<edgevi.size();i++){
// cout<<edgevi[i].first<<" "<<edgevi[i].second<<endl;
//}
//cout<<endl;
cout<<binary();
//dfs1
}
int main(){
input();
solve();
return 0;
}
Compilation message
torrent.cpp: In function 'void dfs1(int, int)':
torrent.cpp:35:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<sus[node].size();i++){
~^~~~~~~~~~~~~~~~~
torrent.cpp: In function 'int dfs2(int, int)':
torrent.cpp:46:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<sus[node].size();i++){
~^~~~~~~~~~~~~~~~~
torrent.cpp:57:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=1;i<v.size();i++){
~^~~~~~~~~
torrent.cpp: In function 'void dfs3(int, int)':
torrent.cpp:69:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<v1.size();i++)edgevi.push_back(v1[i]);
~^~~~~~~~~~
torrent.cpp:72:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<sus[node].size();i++){
~^~~~~~~~~~~~~~~~~
torrent.cpp: In function 'int binary()':
torrent.cpp:110:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(mid<edgevi.size()){
~~~^~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
10 ms |
7420 KB |
Output is correct |
| 2 |
Correct |
10 ms |
7416 KB |
Output is correct |
| 3 |
Correct |
11 ms |
7416 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
931 ms |
26332 KB |
Output is correct |
| 2 |
Correct |
973 ms |
27604 KB |
Output is correct |
| 3 |
Correct |
835 ms |
29000 KB |
Output is correct |
| 4 |
Correct |
952 ms |
28608 KB |
Output is correct |
| 5 |
Correct |
964 ms |
26016 KB |
Output is correct |
| 6 |
Correct |
864 ms |
26612 KB |
Output is correct |
| 7 |
Correct |
911 ms |
29932 KB |
Output is correct |
