# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
569507 | Waratpp123 | Torrent (COI16_torrent) | C++14 | 2073 ms | 21772 KiB |
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;
vector<int> g[300010],tr;
int a,b,par[300010],mark[300010],dp[300010];
int dfs1(int i,int p){
if(i==b) return 1;
for(auto x : g[i]){
if(x==p) continue;
int opr=dfs1(x,i);
if(opr==1){
tr.push_back(x);
return 1;
}
}
return 0;
}
void setpar(int i,int p){
par[i]=p;
for(auto x : g[i]){
if(x==p) continue;
setpar(x,i);
}
}
int dfs(int i,int p){
vector<int> t;
t.clear();
for(auto x : g[i]){
if(x==p||mark[x]==1) continue;
dfs(x,i);
t.push_back(dp[x]);
}
int mx=0,n=t.size();
sort(t.begin(),t.end());
for(int j=0;j<n;j++){
mx=max(mx,t[j]+(n-j));
}
return dp[i]=mx;
}
int main(){
int i,j,n,u,v;
scanf("%d %d %d",&n,&a,&b);
for(i=1;i<=n-1;i++){
scanf("%d %d",&u,&v);
g[u].push_back(v);
g[v].push_back(u);
}
dfs1(a,-1);
setpar(a,-1);
int mid;
int ans=n;
for(mid=0;mid<tr.size();mid++){
mark[tr[mid]]=1;
int suma=dfs(a,-1);
mark[tr[mid]]=0;
mark[par[tr[mid]]]=1;
int sumb=dfs(b,-1);
mark[par[tr[mid]]]=0;
ans=min(ans,max(suma,sumb));
}
printf("%d\n",ans);
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |