Submission #846607

#	Time	Username	Problem	Language	Result	Execution time	Memory
846607		danglayloi1	Torrent (COI16_torrent)	C++17	69 / 100	611 ms	38348 KiB

torrent

#include <bits/stdc++.h>
#define fi first
#define se second
#define inf 0x3f3f3f3f
using namespace std;
using ll = long long;
const int nx=3e5+5;
int n, a, b, p[nx], ans, d, c, g, dp[nx];
bool vis[nx];
vector<int> adj[nx], tmp[nx];
map<pair<int, int>, int> mp;
vector<pair<int, int>> path;
void find(int u)
{
    if(u==b)
        return;
    vis[u]=1;
    for(int v:adj[u])
    {
        if(!vis[v])
        {
            p[v]=u;
            find(v);
        }
    }
}
void dfs(int u, int s, int t)
{
    vis[u]=1;
    for(int v:adj[u])
    {
        if(u==s && v==t)
            continue;
        if(u==t && v==s)
            continue;
        if(!vis[v])
        {
            dfs(v, s, t);
            tmp[u].emplace_back(dp[v]);
        }
    }
    int cur=0;
    sort(tmp[u].begin(), tmp[u].end(), greater<int>());
    for(int i = 0; i < tmp[u].size(); i++)
        cur=max(cur, tmp[u][i]+i+1);
    dp[u]=cur;
}
int cnt(int s, int t)
{
    memset(dp, 0x3f, sizeof(dp));
    memset(vis, 0, sizeof(vis));
    for(int i = 1; i <= n; i++)
        tmp[i].clear();
    dfs(a, s, t);
    dfs(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);
    }
    if(a==b)
        return cout<<cnt(a, a), 0;
    find(a);
    int s=b;
    while(s!=a)
    {
        path.emplace_back(s, p[s]);
        s=p[s];
    }
    d=0;
    c=path.size()-1;
    ans=inf;
    while(d<=c)
    {
        g=(d+c)/2;
        if(cnt(path[g].fi, path[g].se)<ans)
        {
            ans=cnt(path[g].fi, path[g].se);
            d=g+1;
        }
        else c=g-1;
    }
    d=0;
    c=path.size()-1;
    while(d<=c)
    {
        g=(d+c)/2;
        if(cnt(path[g].fi, path[g].se)<ans)
        {
            ans=cnt(path[g].fi, path[g].se);
            c=g-1;
        }
        else d=g+1;
    }
    cout<<ans;
}

Compilation message (stderr)

torrent.cpp: In function 'void dfs(int, int, int)':
torrent.cpp:44:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     for(int i = 0; i < tmp[u].size(); i++)
      |                    ~~^~~~~~~~~~~~~~~

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