oj.uz

Submission #544200

# Submission time Handle Problem Language Result Execution time Memory
544200 2022-04-01T10:08:54 Z levladiator Torrent (COI16_torrent) C++14
100 / 100
 978 ms 53256 KB 
#include <bits/stdc++.h>
#define pb push_back
#define pf push_front
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define EPSILON 0.000001
#define CH (*s-'a')

using namespace std;

const ll NMAX = 3e5 + 5, INF = 1e18, MOD = 1e9 + 7, MMAX = 1e2 + 5, inf = 1e9;

ifstream fin("date.in");
ofstream fout("date.out");

int N,A,B;
int cost[NMAX],par[NMAX];
vector<int> chain;
set<int> adj[NMAX];

void path(int node,int prev)
{
    par[node]=prev;
    if(node==B)
    {
        int x=B;
        while(x!=A)
        {
            chain.pb(x);
            x=par[x];
        }
        chain.pb(A);
        return;
    }
    for(auto son : adj[node])
    {
        if(son==prev)
            continue;

        path(son,node);
    }
}

void dfs(int node,int prev)
{
    for(auto son : adj[node])
    {
        if(son==prev)
            continue;
        dfs(son,node);
    }
    vector<int> aux;
    for(auto son : adj[node])
    {
        if(son==prev)
            continue;
        aux.pb(cost[son]);
    }
    int sons=aux.size();
    sort(aux.begin(),aux.end());
    for(auto x : aux)
    {
        cost[node]=max(cost[node],x+sons);
        sons--;
    }
}

int main()
{
    cin.tie ( 0 )->sync_with_stdio ( 0 );
    cin.tie ( NULL );
    cout.tie ( NULL );

    cin>>N>>A>>B;
    for(int i=1;i<N;i++)
    {
        int a,b;
        cin>>a>>b;
        adj[a].insert(b);
        adj[b].insert(a);
    }
    path(A,0);
    reverse(chain.begin(),chain.end());
    int lo=0,hi=chain.size()-2;
    int ans=1e9;
    while(lo<=hi)
    {
        for(int i=1;i<=N;i++)
        {
            cost[i]=0;
        }
        int mid=(lo+hi)/2;
        int c=chain[mid],d=chain[mid+1];
        adj[c].erase(d);
        adj[d].erase(c);
        dfs(A,0);
        dfs(B,0);
        if(cost[A]<=cost[B])
        {
            lo=mid+1;
        }
        else hi=mid-1;
        ans=min(ans,max(cost[A],cost[B]));
        adj[c].insert(d);
        adj[d].insert(c);
    }
    cout<<ans;

    return 0;
}

Subtask #1
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14420 KB Output is correct
2 Correct 9 ms 14548 KB Output is correct
3 Correct 9 ms 14436 KB Output is correct

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 877 ms 46272 KB Output is correct
2 Correct 806 ms 51524 KB Output is correct
3 Correct 978 ms 52808 KB Output is correct
4 Correct 672 ms 52360 KB Output is correct
5 Correct 707 ms 50216 KB Output is correct
6 Correct 743 ms 50680 KB Output is correct
7 Correct 699 ms 53256 KB Output is correct