# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
28746 | samir_droubi | Torrent (COI16_torrent) | C++14 | 239 ms | 35172 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;
int n;
const int mxn=(3e5)+5;
int a,b;
vector<int>tr[mxn];
int dep[mxn];
int pa[mxn];
bool path[mxn];
void dfs(int v,int p)
{
for(int i=0;i<tr[v].size();++i)
{
int u=tr[v][i];
if(u==p)continue;
dep[u]=dep[v]+1;
pa[u]=v;
dfs(u,v);
}
}
void lca()
{
int x=a;
int y=b;
path[x]=true;
path[y]=true;
if(dep[x]>dep[y])swap(y,x);
while(dep[y]!=dep[x])
{
y=pa[y];
path[y]=true;
}
if(x==y)return;
while(pa[x]!=pa[y])
{
x=pa[x];
y=pa[y];
path[x]=true;
path[y]=true;
}
path[pa[x]]=true;
}
int dp[mxn];
bool cmp(int x,int y)
{
return dp[x]>dp[y];
}
void dfs1(int v,int p)
{
dp[v]=0;
for(int i=0;i<tr[v].size();++i)
{
int u=tr[v][i];
if(u==p||path[u])continue;
dfs1(u,v);
}
sort(tr[v].begin(),tr[v].end(),cmp);
int c=0;
for(int i=0;i<tr[v].size();++i)
{
int u=tr[v][i];
if(u==p||path[u])continue;
++c;
dp[u]+=c;
dp[v]=max(dp[v],dp[u]);
}
}
vector<int>vv[mxn];
bool explored[mxn];
bool check(int T)
{
memset(explored,0,sizeof explored);
for(int i=0;i<mxn;++i)vv[i].clear();
vv[0].push_back(a);
vv[0].push_back(b);
for(int i=0;i<T;++i)
{
for(int j=0;j<vv[i].size();++j)
{
int v=vv[i][j];
if(explored[v])continue;
explored[v]=true;
if(dp[v]+i>T)return false;
int del=1;
int node=-1;
for(int k=0;k<tr[v].size();++k)
{
int u=tr[v][k];
if(path[u])
{
if(!explored[u])node=u;
continue;
}
if(dp[u]+i==T)++del;
}
if(node==-1)continue;
if(del+i>=T)continue;
vv[del+i].push_back(node);
}
}
bool ok=true;
for(int i=1;i<=n;++i)
if(path[i]&&!explored[i])ok=false;
return ok;
}
void bs()
{
int l=1;
int r=n;
int ans=-1;
while(l<=r)
{
int md=(l+r)/2;
if(check(md))
{
ans=md;
r=md-1;
}
else l=md+1;
}
printf("%d\n",ans);
}
int main()
{
scanf("%d%d%d",&n,&a,&b);
for(int i=0;i<n-1;++i)
{
int x,y;
scanf("%d%d",&x,&y);
tr[x].push_back(y);
tr[y].push_back(x);
}
dfs(1,1);
lca();
for(int i=1;i<=n;++i)
{
if(!path[i])continue;
dfs1(i,i);
}
bs();
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |