Submission #489298

#	Time	Username	Problem	Language	Result	Execution time	Memory
489298		mdn2002	Race (IOI11_race)	C++14	100 / 100	2363 ms	146184 KiB

race

#include<bits/stdc++.h>
#include "race.h"
using namespace std;
long long n , k , mn = 1e9 , dis [200005] , dp [200005] , in [200005] , ot [200005] , siz [200005] , tmm;
int H [200005][2] , L [200005];
vector < int > ord;
vector < pair < int , int > > gr [200005];
map < long long , multiset < int > > cnt;
void go ( int x , int p )
{
    in [x] = tmm ++;
    dp [x] = dp [p] + 1;
    siz [x] = 1;
    ord . push_back ( x );
    for ( auto pr : gr [x] )
    {
        long long u = pr . first , c = pr . second;
        if ( u == p ) continue;
        dis [u] = dis [x] + c;
        go ( u , x );
        siz [x] += siz [u];
    }
    ot [x] = tmm;
}
void dfs ( int x , int p , int keep )
{
    int mx = -1 , big = -1;
    for ( auto pr : gr [x] )
    {
        int u = pr . first;
        if ( u == p ) continue;
        if ( mx < siz [u] )
        {
            mx = siz [u];
            big = u;
        }
    }
    for ( auto pr : gr [x] )
    {
        int u = pr . first;
        if ( u == p || u == big ) continue;
        dfs ( u , x , 0 );
    }
    if ( big != -1 ) dfs ( big , x , 1 );

    for ( auto pr : gr [x] )
    {
        int u = pr . first;
        if ( u == p || u == big ) continue;
        for ( int j = in [u] ; j < ot [u] ; j ++ )
        {
            int v = ord [j];
            long long dif = dis [v] - dis [x];
            if ( cnt [ k - dif + dis [x] ] . size () == 0 ) continue;
            int bst = * cnt [ k - dif + dis [x] ] . begin ();
            mn = min ( mn , dp [v] + bst - 2 * dp [x] );
        }
        for ( int j = in [u] ; j < ot [u] ; j ++ )
        {
            int v = ord [j];
            cnt [ dis [v] ] . insert ( dp [v] );
        }
    }
    if ( cnt [ k + dis [x] ] . size () )
    {
        int bst = * cnt [ k + dis [x] ] . begin ();
        mn = min ( mn , bst - dp [x] );
    }
    cnt [ dis [x] ] . insert ( dp [x] );
    if ( keep == 0 )
    {
        for ( int j = in [x] ; j < ot [x] ; j ++ )
        {
            int v = ord [j];
            cnt [ dis [v] ] . erase ( cnt [ dis [v] ] . lower_bound ( dp [v] ) );
        }
    }
}
int best_path( int N , int K , int H [][2] , int L [] )
{
    n = N , k = K;
    for( int i = 0 ; i < n - 1 ; i ++ )
    {
        int x = H [i][0] + 1 , y = H [i][1] + 1;
        gr [x] . push_back ( { y , L [i] } );
        gr [y] . push_back ( { x , L[i] } );
    }
    go ( 1 , 0 );
    dfs ( 1 , 0 , 0 );
    if ( mn != 1e9 ) return mn;
    else return -1;
}

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 22 / 22
• Subtask 4: 57 / 57