Submission #1185780

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185780		Hanksburger	Torrent (COI16_torrent)	C++20	100 / 100	95 ms	68652 KiB

torrent

#include <bits/stdc++.h>
using namespace std;
int dp[1050005], res[1050005], onpath[1050005], n;
vector<int> adj[1050005], tmp[1050005], path;
void dfs(int u, int p)
{
    vector<int> t;
    for (int v:adj[u])
    {
        if (v==p)
            continue;
        dfs(v, u);
        t.push_back(dp[v]);
    }
    sort(t.begin(), t.end(), greater<int>());
    dp[u]=0;
    for (int i=0; i<t.size(); i++)
        dp[u]=max(dp[u], t[i]+i+1);
}
int findPath(int u, int p)
{
    for (int v:adj[u])
    {
        if (v==p)
            continue;
        if (v==n)
            return 1;
        path.push_back(v);
        if (findPath(v, u))
            return 1;
        path.pop_back();
    }
    return 0;
}
void calc(int mid)
{
    for (int i=mid; i>=0; i--)
    {
        int u=path[i];
        if (i==mid)
        {
            dp[u]=0;
            for (int j=0; j<tmp[u].size(); j++)
                dp[u]=max(dp[u], tmp[u][j]+j+1);
        }
        else
        {
            int special=dp[path[i+1]], done=0;
            dp[u]=0;
            for (int j=0; j<tmp[u].size(); j++)
            {
                if (!done && special>tmp[u][j])
                {
                    dp[u]=max(dp[u], special+j+1);
                    done=1;
                }
                dp[u]=max(dp[u], tmp[u][j]+j+1+done);
            }
            if (!done)
                dp[u]=max(dp[u], special+(int)tmp[u].size()+1);
        }
    }
    for (int i=mid+1; i<path.size(); i++)
    {
        int u=path[i];
        if (i==mid+1)
        {
            dp[u]=0;
            for (int j=0; j<tmp[u].size(); j++)
                dp[u]=max(dp[u], tmp[u][j]+j+1);
        }
        else
        {
            int special=dp[path[i-1]], done=0;
            dp[u]=0;
            for (int j=0; j<tmp[u].size(); j++)
            {
                if (!done && special>tmp[u][j])
                {
                    dp[u]=max(dp[u], special+j+1);
                    done=1;
                }
                dp[u]=max(dp[u], tmp[u][j]+j+1+done);
            }
            if (!done)
                dp[u]=max(dp[u], special+(int)tmp[u].size()+1);
        }
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int tmp1, tmp2;
    cin >> n >> tmp1 >> tmp2;
    for (int i=1; i<n; i++)
    {
        int u, v;
        cin >> u >> v;
        if (u==tmp1)
            u=1;
        else if (u==1)
            u=tmp1;
        else if (u==tmp2)
            u=n;
        else if (u==n)
            u=tmp2;
        if (v==tmp1)
            v=1;
        else if (v==1)
            v=tmp1;
        else if (v==tmp2)
            v=n;
        else if (v==n)
            v=tmp2;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1, 0);
    path.push_back(1);
    findPath(1, 0);
    path.push_back(n);
    for (int i=0; i<path.size(); i++)
        onpath[path[i]]=1;
    for (int u=1; u<=n; u++)
    {
        if (!onpath[u])
            continue;
        for (int j=0; j<adj[u].size(); j++)
        {
            int v=adj[u][j];
            if (!onpath[v])
                tmp[u].push_back(dp[v]);
        }
        sort(tmp[u].begin(), tmp[u].end(), greater<int>());
    }
    int l=-1, r=path.size()-2;
    while (l<r)
    {
        int mid=(l+r+1)/2;
        calc(mid);
        res[mid]=max(dp[1], dp[n])+1;
        if (dp[1]<dp[n])
            l=mid;
        else
            r=mid-1;
    }
    int ans=1e9;
    if (l>=0)
    {
        if (res[l])
            ans=min(ans, res[l]-1);
        else
        {
            calc(l);
            ans=min(ans, dp[n]);
        }
    }
    if (l+3<=path.size())
    {
        if (res[l+1])
            ans=min(ans, res[l+1]-1);
        else
        {
            calc(l+1);
            ans=min(ans, dp[1]);
        }
    }
    cout << ans;
}

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