Submission #1020098

#	Time	Username	Problem	Language	Result	Execution time	Memory
1020098		DucNguyen2007	Torrent (COI16_torrent)	C++14	0 / 100	2024 ms	57168 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]=-inf;
        dp2[i]=-inf;
    }
}
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 dp1[a]+dp2[b];
}
int main()
{
    //freopen("","r",stdin);
    //freopen("","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);
    }
    pre_dfs(a,0);
    vec.push_back(0);
    pre_dfs1(a,0);
    ll ans=inf;
    for(auto i:vec)
    {
        if(i!=0&&i!=a)
        {
            ans=min(ans,solve(i));
            //cout<<i<<" "<<solve(i)<<'\n';
        }
    }
    cout<<ans;
}

Compilation message (stderr)

torrent.cpp: In function 'void clr()':
torrent.cpp:73:16: warning: overflow in conversion from 'long long int' to 'int' changes value from '-2000000000000000000' to '-1321730048' [-Woverflow]
   73 |         dp1[i]=-inf;
      |                ^~~~
torrent.cpp:74:16: warning: overflow in conversion from 'long long int' to 'int' changes value from '-2000000000000000000' to '-1321730048' [-Woverflow]
   74 |         dp2[i]=-inf;
      |                ^~~~
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: 0 / 31
• Subtask 2: 0 / 69