Submission #755556

#	Time	Username	Problem	Language	Result	Execution time	Memory
755556		bgnbvnbv	Torrent (COI16_torrent)	C++14	100 / 100	609 ms	49484 KiB

torrent

#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<int,int>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=int;
const ll maxN=3e5+10;

const ll mod=1e9+7;
ll dp[maxN];
vector<ll>g[maxN];
ll sz,vc[maxN];
void dfs1(ll u,ll p,ll cam)
{
    dp[u]=0;
    for(auto v:g[u])
    {
        if(v!=p&&v!=cam)
        {
            dfs1(v,u,cam);
        }
    }
    sz=0;
    for(auto v:g[u])
    {
        if(v!=p&&v!=cam)
        {
            sz++;
            vc[sz]=dp[v];
        }
    }
    sort(vc+1,vc+sz+1,greater<ll>());
    for(int i=1;i<=sz;i++) dp[u]=max(dp[u],vc[i]+i);
}
ll P[maxN][19],h[maxN];
ll anc(ll u,ll k)
{
    for(int i=18;i>=1;i--) if(k>>i&1) u=P[u][i];
    return u;
}
void dfs(ll u,ll p)
{
    P[u][0]=p;
    for(int i=1;i<=18;i++) P[u][i]=P[P[u][i-1]][i-1];
    for(int v:g[u])
    {
        if(v!=p)
        {
            h[v]=h[u]+1;
            dfs(v,u);

        }
    }
}
ll b,a;
ll cal(ll mid)
{
    ll x=anc(b,mid);
    ll y=P[x][0];
    dfs1(a,a,x);
    dfs1(b,b,y);
    return max(dp[a],dp[b]);
}
ll n;
void solve()
{
    cin >> n >> a >> b;
    for(int i=1;i<n;i++)
    {
        ll u,v;
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }
    dfs(a,a);
    ll dis=h[b]-h[a];
    ll low=1,high=dis-1;
    while(low<=high)
    {
        ll mid=low+high>>1;
        cal(mid);
        if(dp[b]>dp[a]) high=mid-1;
        else low=mid+1;
    }
    ll ans=cal(high);
    //cout << high<<'\n';
    low=0,high=dis-2;
    while(low<=high)
    {
        ll mid=low+high>>1;
        cal(mid);
        if(dp[b]>=dp[a]) high=mid-1;
        else low=mid+1;
    }
    ans=min(ans,cal(low));
    cout << ans;
}
int main()
{
    fastio
    //freopen(TASKNAME".INP","r",stdin);
    //freopen(TASKNAME".OUT","w",stdout);
    solve();
}

Compilation message (stderr)

torrent.cpp: In function 'void solve()':
torrent.cpp:84:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   84 |         ll mid=low+high>>1;
      |                ~~~^~~~~
torrent.cpp:94:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   94 |         ll mid=low+high>>1;
      |                ~~~^~~~~

• Subtask 1: 31 / 31
• Subtask 2: 69 / 69