Submission #846638

#	Time	Username	Problem	Language	Result	Execution time	Memory
846638		vjudge1	Torrent (COI16_torrent)	C++17	100 / 100	358 ms	41460 KiB

torrent

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e7;
ll n,a,b,x,y,check[300005],trace[300005],c,dist[300005],canh,moc,pos=-1,hao,res=mod;
vector<ll> ed[300005],pa,dp[300005];
void dfs(int u)
{
    check[u]=1;
    for (auto it: ed[u])
    {
        if (check[it]==0)
        {
            dfs(it);
            trace[it]=u;
        }
    }
}
void dpontree(int u,int v)
{
    dist[u]=0;
    if (u==v) return;
    check[u]=1;
    for (auto it: ed[u])
    {
        if (check[it]==0)
        {
            dpontree(it,v);
            dp[u].push_back(dist[it]);
        }
    }
    sort(dp[u].begin(),dp[u].end());
    canh=0;
    moc=1;
    for (int i=dp[u].size()-1;i>=0;--i)
    {
        canh=max(canh,dp[u][i]+moc);
        moc++;
    }
    dist[u]=canh;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin>>n>>a>>b;
    c=b;
    for (int i=1;i<n;++i)
    {
        cin>>x>>y;
        ed[x].push_back(y);
        ed[y].push_back(x);
    }
    dfs(a);
    while (b!=0)
    {
        pa.push_back(b);
        b=trace[b];
    }
    b=c;
    int l=0,r=pa.size()-2;
    while (l<=r)
    {
        int mid=(l+r)/2;
        for (int i=1;i<=n;++i) dp[i].clear();
        memset(check,0,sizeof(check));
        dpontree(b,pa[mid+1]);
        dpontree(a,pa[mid]);
        res=min(res,max(dist[b],dist[a]));
        if (dist[b]<=dist[a])
        {
            l=mid+1;
        }
        else r=mid-1;
    }
//    if (pos==-1)
//    {
//        for (int i=1;i<=n;++i) dp[i].clear();
//        memset(check,0,sizeof(check));
//        dpontree(b,pa[1]);
//        cout<<dist[b];
//        return 0;
//    }
//    else
//    {
//        for (int i=1;i<=n;++i) dp[i].clear();
//        memset(check,0,sizeof(check));
//        dpontree(b,pa[pos+1]);
//        dpontree(a,pa[pos]);
//        hao=dist[a];
//        if (pos+2<pa.size())
//        {
//        for (int i=1;i<=n;++i) dp[i].clear();
//        memset(check,0,sizeof(check));
//        dpontree(b,pa[pos+2]);
//        dpontree(a,pa[pos+1]);
//        hao=min(hao,dist[b]);
//        }
//        cout<<hao;
//        return 0;
//    }
       cout<<res;
}

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