Submission #1097064

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097064		DucNguyen2007	Torrent (COI16_torrent)	C++14	100 / 100	793 ms	58388 KiB

torrent

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pll pair<ll,ll>
#define fi first
#define se second
const int maxN=3e5+5;
const ll inf=2e18;
int n,a,b,dp1[maxN+1],dp2[maxN+1],h[maxN+1];
vector<int> adj[maxN+1],adj_a[maxN+1],adj_b[maxN+1],vec;
bool ck[maxN+1];
void pre_dfs(int u,int p)
{
    if(u==b)
    {
        ck[u]=true;
        return;
    }
    for(auto v:adj[u])
    {
        if(v!=p)
        {
            h[v]=h[u]+1;
            pre_dfs(v,u);
            if(ck[v])
            {
                ck[u]=true;
            }
        }
    }
}
void pre_dfs1(int u,int p)
{
    vec.push_back(u);
    for(auto v:adj[u])
    {
        if(v!=p&&ck[v])
        {
            pre_dfs1(v,u);
        }
    }
}
void build(int u,int p,int pos,bool ok)
{
    for(auto v:adj[u])
    {
        if(v!=p)
        {
            if(ok&&h[v]>h[pos])
            {
                adj_b[u].push_back(v);
                adj_b[v].push_back(u);
            }
            else
            {
                if(v!=pos)
                {
                    adj_a[u].push_back(v);
                    adj_a[v].push_back(u);
                }
            }
            build(v,u,pos,(ok||(v==pos)));
        }
    }
}
void clr()
{
    for(int i=1;i<=n;i++)
    {
        adj_a[i].clear();
        adj_b[i].clear();
        dp1[i]=0;
        dp2[i]=0;
    }
}
void dfs1(int u,int p)
{
    vector<int> ve;
    for(auto v:adj_a[u])
    {
        if(v!=p)
        {
            dfs1(v,u);
            ve.push_back(v);
        }
    }
    sort(ve.begin(),ve.end(),[&](int x,int y)
    {
        return dp1[x]>dp1[y];
    });
    dp1[u]=0;
    for(int i=1;i<=ve.size();i++)
    {
        int v=ve[i-1];
        dp1[u]=max(dp1[u],dp1[v]+i);
    }
}
void dfs2(int u,int p)
{
    vector<int> ve;
    for(auto v:adj_b[u])
    {
        if(v!=p)
        {
            dfs2(v,u);
            ve.push_back(v);
        }
    }
    sort(ve.begin(),ve.end(),[&](int x,int y)
    {
        return dp2[x]>dp2[y];
    });
    dp2[u]=0;
    for(int i=1;i<=ve.size();i++)
    {
        int v=ve[i-1];
        dp2[u]=max(dp2[u],dp2[v]+i);
    }
}
ll solve(int pos)
{
    clr();
    build(a,0,pos,0);
    dfs1(a,0);
    dfs2(b,0);
    return max(dp1[a],dp2[b]);
}
bool check(int pos)
{
    clr();
    build(a,0,pos,0);
    dfs1(a,0);
    dfs2(b,0);
    return (dp1[a]>dp2[b]);
}
int main()
{
    //freopen("torrent.inp","r",stdin);
    //freopen("torrent.out","w",stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>a>>b;
    if(a>b)
    {
        swap(a,b);
    }
    for(int i=1;i<n;i++)
    {
        int u,v;
        cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    h[1]=1;
    pre_dfs(a,0);
    pre_dfs1(a,0);
    ll ans=inf;
    if(n<=1000)
    {
        for(auto i:vec)
        {
            if(i!=0&&i!=a)
            {
                ans=min(ans,solve(i));
                //cout<<i<<" "<<solve(i)<<'\n';
            }
        }
    }
    else
    {
        ll l=1,r=vec.size()-1;
        while(l<r)
        {
            ll mid=(l+r)/2;
            ll tmp1=solve(vec[mid]),tmp2=solve(vec[mid+1]);
            ans=min(ans,max(tmp1,tmp2));
            if(tmp1>tmp2)
            {
                l=mid+1;
            }
            else r=mid-1;
        }
    }
    cout<<ans;
}

Compilation message (stderr)

torrent.cpp: In function 'void dfs1(int, int)':
torrent.cpp:93:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |     for(int i=1;i<=ve.size();i++)
      |                 ~^~~~~~~~~~~
torrent.cpp: In function 'void dfs2(int, int)':
torrent.cpp:115:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |     for(int i=1;i<=ve.size();i++)
      |                 ~^~~~~~~~~~~

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