Submission #674696

#	Time	Username	Problem	Language	Result	Execution time	Memory
674696		mdn2002	Valley (BOI19_valley)	C++14	100 / 100	474 ms	54332 KiB

valley

#include<bits/stdc++.h>
using namespace std;
long long n , s , q , e , dp [100005] , pr [100005] , st [100005][23] , sum [100005] , stt [100005][23];
vector < pair < int , int > > gr [100005] , edg;
void go ( int x , int p )
{
    dp [x] = dp [p] + 1;
    st [x][0] = p;
    for ( auto xx : gr [x] )
    {
        int u = xx . first;
        if ( u == p ) continue;
        sum [u] = sum [x] + xx . second;
        go ( u , x );
        stt [x][0] = min ( stt [x][0] , stt [u][0] + xx . second );
    }
}
int lca ( int x , int y )
{
    if ( dp [x] > dp [y] ) swap ( x , y );
    int dif = dp [y] - dp [x];
    for ( int i = 0 ; i < 21 ; i ++ )
    {
        if ( ( dif & ( 1 << i ) ) ) y = st [y][i];
    }
    if ( x == y ) return x;
    for ( int i = 21 ; i >= 0 ; i -- )
    {
        if ( st [x][i] != st [y][i] )
        {
            x = st [x][i];
            y = st [y][i];
        }
    }
    return st [x][0];
}
int main()
{
    cin >> n >> s >> q >> e;
    for ( int i = 0 ; i < n - 1 ; i ++ )
    {
        int x , y , z;
        cin >> x >> y >> z;
        edg . push_back ( { x , y } );
        gr [x] . push_back ( { y , z } );
        gr [y] . push_back ( { x , z } );
    }
    for ( int i = 1 ; i <= n ; i ++ ) stt [i][0] = 1e16;
    for ( int i = 0 ; i < s ; i ++ )
    {
        int x;
        cin >> x;
        stt [x][0] = 0;
    }
    go ( e , 0 );
    for ( int i = 1 ; i <= 21 ; i ++ )
    {
        for ( int j = 1 ; j <= n ; j ++ )
        {
            long long nxt = st [j][ i - 1 ] , dis = sum [j] - sum [nxt];
            st [j][i] = st [nxt][ i - 1 ];
            stt [j][i] = min ( stt [j][ i - 1 ] , stt [nxt][ i - 1 ] + dis );
        }
    }
    while ( q -- )
    {
        int x , y;
        cin >> x >> y;
        int a = edg [ x - 1 ] . first , b = edg [ x - 1 ] . second;
        if ( dp [a] < dp [b] ) a = b;

        if ( lca ( y , a ) != a )
        {
            cout << "escaped" << endl;
            continue;
        }

        long long dif = dp [y] - dp [a] + 1 , ans = 1e17 , oy = y;
        for ( int i = 0 ; i <= 21 ; i ++ )
        {
            if ( ( dif & ( 1 << i ) ) )
            {
                long long ad = sum [oy] - sum [y];
                ans = min ( ans , ad + stt [y][i] );
                y = st [y][i];
            }
        }
        if ( ans >= 1e16 ) cout << "oo" << endl;
        else cout << ans << endl;
    }

}

• Subtask 1: 9 / 9
• Subtask 2: 27 / 27
• Subtask 3: 23 / 23
• Subtask 4: 41 / 41