Submission #755549

#	Time	Username	Problem	Language	Result	Execution time	Memory
755549		bgnbvnbv	Torrent (COI16_torrent)	C++14	0 / 100	522 ms	47628 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 inf=1e18;
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;
        if(cal(mid)<cal(mid-1)) low=mid+1;
        else high=mid-1;
    }
    cout << cal(high);

}
int main()
{
    fastio
    //freopen(TASKNAME".INP","r",stdin);
    //freopen(TASKNAME".OUT","w",stdout);
    solve();
}

Compilation message (stderr)

torrent.cpp:12:14: warning: overflow in conversion from 'double' to 'll' {aka 'int'} changes value from '1.0e+18' to '2147483647' [-Woverflow]
   12 | const ll inf=1e18;
      |              ^~~~
torrent.cpp: In function 'void solve()':
torrent.cpp:84:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   84 |         ll mid=low+high>>1;
      |                ~~~^~~~~

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