제출 #474542

#제출 시각아이디문제언어결과실행 시간메모리
474542bin1st090104Torrent (COI16_torrent)C++11
100 / 100
416 ms22940 KiB
#include <bits/stdc++.h> using namespace std; int const maxN=3e5; int N,A,B; vector<int> Adj[maxN+3]; int Cha[maxN+3],f[maxN+3]; int Tmp_array[maxN+3]; int Color[maxN+3]; void Dfs1(int u){ for(int v:Adj[u]){ if(v==Cha[u]){ continue; } Cha[v]=u; Dfs1(v); } return ; } int Path[maxN+3]; void Dfs2(int u,int x,int p=-1){ for(int v:Adj[u]){ if(v==x||v==p){ continue; } Dfs2(v,x,u); } int Cnt=0; for(int v:Adj[u]){ if(v==x||v==p){ continue; } Tmp_array[++Cnt]=f[v]; } sort(Tmp_array+1,Tmp_array+Cnt+1,greater<int>()); f[u]=0; for(int i=1;i<=Cnt;++i){ f[u]=max(f[u],i+Tmp_array[i]); } return ; } int main(){ cin.tie(nullptr)->sync_with_stdio(false); cin>>N>>A>>B; for(int i=1;i<N;++i){ int u,v; cin>>u>>v; Adj[u].push_back(v); Adj[v].push_back(u); } Dfs1(A); int Len=0; { int u=B; do{ Path[++Len]=u; if(u==A){ break; } u=Cha[u]; } while(1); } int l=1,r=Len-1,m,Res=1e9+7; while(l<=r){ m=(l+r)>>1; Dfs2(A,Path[m]); Dfs2(B,Cha[Path[m]]); int x=f[B]; int y=f[A]; Res=min(Res,max(x,y)); if(x<y){ l=m+1; } else{ r=m-1; } } cout<<Res; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...