Submission #1131519

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131519		danglayloi1	Torrent (COI16_torrent)	C++17	0 / 100	337 ms	24168 KiB

torrent

#include <bits/stdc++.h>
#define ii pair<int, int>
#define fi first
#define se second
#define inf 0x3f3f3f3f
using namespace std;
using ll = long long;
const ll mod=1e9+7;
const int nx=3e5+5;
int n, m, a, b, par[nx], dp[nx];
vector<int> adj[nx], path;
void go(int u)
{
    for(int v:adj[u])
        if(v!=par[u])
            par[v]=u, go(v);
}
int dfs(int p, int u, int s, int t)
{
    vector<int> tmp;
    tmp.clear();
    for(int v:adj[u])
    {
        if(ii(u, v)==ii(s, t) || ii(u, v)==ii(t, s) || v==p)
            continue;
        tmp.emplace_back(dfs(u, v, s, t));
    }
    dp[u]=0;
    sort(tmp.begin(), tmp.end(), greater<int>());
    for(int i = 0; i < tmp.size(); i++)
        dp[u]=max(dp[u], tmp[i]+i+1);
    return dp[u];
}
int solve(int s)
{
    return max(dfs(0, a, s, par[s]), dfs(0, b, s, par[s]));
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    // freopen("tdl.inp", "r", stdin);
    // freopen("tdl.out", "w", stdout);
    cin>>n>>a>>b;
    for(int i = 1; i < n; i++)
    {
        int u, v;
        cin>>u>>v;
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }
    // cin>>m;
    // if(m==1) cin>>a;
    // else cin>>a>>b;
    // if(m==1 || a==b)
    // {
    //     dfs(0, a, 0, 0);
    //     return cout<<dp[a], 0;
    // }
    if(a==b)
        return cout<<dfs(0, a, 0, 0), 0;
    go(a);
    for(int i = b; i != a; i = par[i])
        path.emplace_back(i);
    int d=0, c=path.size()-1, g, pos=0;
    while(d<=c)
    {
        g=(d+c)/2;
        if(dfs(0, a, g, par[g])-dfs(0, b, g, par[g])>0) pos=g, d=g+1;
        else c=g-1;
    }
    int ans=solve(path[pos]);
    if(pos>0) ans=min(ans, solve(path[pos-1]));
    if(pos<(int)path.size()-1) ans=min(ans, solve(path[pos+1]));
    cout<<ans;
}

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