Submission #846636

#	Time	Username	Problem	Language	Result	Execution time	Memory
846636		vjudge1	Torrent (COI16_torrent)	C++17	0 / 100	372 ms	39132 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;
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)
{
    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]);
        if (dist[b]<=dist[a])
        {
            pos=mid;
            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;
    }

}

Compilation message (stderr)

torrent.cpp: In function 'int main()':
torrent.cpp:90:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |         if (pos+2<pa.size())
      |             ~~~~~^~~~~~~~~~

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