oj.uz

Submission #846611

# Submission time Handle Problem Language Result Execution time Memory
846611 2023-09-08T07:00:45 Z vjudge1 Torrent (COI16_torrent) C++17
100 / 100
 561 ms 38344 KB 
#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];
    }
    ans=inf;
    if(n<=1000)
    {
        for(auto it:path)
            ans=min(ans, cnt(it.fi, it.se));
        return cout<<ans, 0;
    }
    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);
            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

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
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 17188 KB Output is correct
2 Correct 7 ms 16984 KB Output is correct
3 Correct 9 ms 16984 KB Output is correct

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 541 ms 33808 KB Output is correct
2 Correct 555 ms 36052 KB Output is correct
3 Correct 546 ms 35976 KB Output is correct
4 Correct 561 ms 38324 KB Output is correct
5 Correct 498 ms 33992 KB Output is correct
6 Correct 461 ms 34252 KB Output is correct
7 Correct 361 ms 38344 KB Output is correct