Submission #544195

#	Time	Username	Problem	Language	Result	Execution time	Memory
544195		levladiator	Torrent (COI16_torrent)	C++14	0 / 100	2 ms	1364 KiB

torrent

#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 = 3e3 + 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);
    }
}

int dfs(int node,int prev)
{
    for(auto son : adj[node])
    {
        if(son==prev)
            continue;
        dfs(son,node);
    }
    multiset<int> aux;
    for(auto son : adj[node])
    {
        if(son==prev)
            continue;
        aux.insert(cost[son]);
    }
    int sons=aux.size();
    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;
}

Compilation message (stderr)

torrent.cpp: In function 'int dfs(int, int)':
torrent.cpp:67:1: warning: no return statement in function returning non-void [-Wreturn-type]
   67 | }
      | ^

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