Submission #1131270

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131270		danglayloi1	Torrent (COI16_torrent)	C++17	0 / 100	29 ms	7748 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=1e5+5;
int n, m, a, b, par[nx], dp[nx];
vector<int> adj[nx];
vector<ii> path;
void go(int u)
{
    for(int v:adj[u])
        if(v!=par[u])
            par[v]=u, go(v);
}
void 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;
        par[v]=u;
        dfs(u, v, s, t);
        tmp.emplace_back(dp[v]);
    }
    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);
}
int solve(int s, int t)
{
    dfs(0, a, s, t);
    dfs(0, b, s, t);
    return max(dp[a], dp[b]);
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    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)
    {
        dfs(0, a, 0, 0);
        return cout<<dp[a], 0;
    }
    go(a);
    path.emplace_back(b, par[b]);
    while(par[b]!=a)
        b=par[b], path.emplace_back(b, par[b]);
    int d=0, c=path.size()-1, g;
    while(d+1<c)
    {
        g=(d+c)>>1;
        int x=solve(path[g].fi, path[g].se);
        int y=solve(path[g+1].fi, path[g+1].se);
        if(x>y) d=g;
        else if(x==y) return cout<<x, 0;
        else c=g;
    }
    cout<<max(solve(path[d].fi, path[d].se), solve(path[c].fi, path[c].se));
}

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