Submission #908257

#	Time	Username	Problem	Language	Result	Execution time	Memory
908257		I_FloPPed21	Valley (BOI19_valley)	C++14	100 / 100	246 ms	63772 KiB

valley

#include <iostream>
#include <vector>
using namespace std;
int n, s, q, e;
bool shop[300005];
vector<pair<int,int>> adj[300005];
vector<pair<int,int>> edges;
long long dist [300005], tin[300005],tout[300005],close[300005];
vector<int> ord;
void dfs(int nod,int p)
{
    ord.push_back(nod);
    tin[nod] = ord.size();
    for ( auto u : adj[nod])
    {
        if ( u.first != p)
        {
            dist[u.first] = dist[nod] + u.second;
            dfs(u.first,nod);
        }
    }
    if ( shop [nod] == 1 )
        close[nod] =dist[nod];
    else
        close[nod] = 1e18;

    for ( auto u :adj[nod])
        if ( u.first != p )
            close[nod] = min (close[nod], close[u.first]);
    tout[nod] = ord.size();
}
long long jmp[300005][21] , mag[300005][21];
void lift(int nod ,int p)
{
    jmp[nod][0] = p;
    mag[nod][0] = close[nod];

    for (int k = 1; k <= 19 ; k ++)
    {
        jmp[nod][k] = jmp[jmp[nod][k-1]][k-1];
        mag[nod][k] = min(mag[nod][k-1] , mag[jmp[nod][k-1]][k-1]);
    }

    for ( auto u : adj[nod])
        if ( u.first != p)
        lift(u.first,nod);

}

long long cost(int nod ,int tg )
{
    long long ans = 1e18;

    int d = nod ;
    for( int k = 18 ; k >= 0 ; k -- )
    {
        int a = jmp[d][k];

        if ( tin[a] >= tin [tg] && tout[a] <= tout[tg] )
        {
            ans =min ( ans , mag[d][k]);
            d = jmp[d][k];
        }
    }
    ans = min ( ans , close[tg]);

    return ans + dist[nod];

}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >>n>>s>>q>>e;
    for(int i = 1; i < n ; i ++ )
    {
        int a, b, c;
        cin >> a>> b>> c;
        adj[a].push_back({b,c});
        adj[b].push_back({a,c});
        edges.push_back({a,b});
    }

    for( int i = 1; i <= s; i ++)
    {
        int a;
        cin >> a;
        shop[a] =true;
    }
        dfs(e,0);
        for ( int i = 1; i <= n ; i ++ )
            close [i] -= 2 * dist[i];
        lift(e,0);

        for ( int i = 1; i <= q; i ++ )
        {
            int l , r;
            cin >> l >> r;
            l -- ;
            int a = edges[l].first;
            int b = edges[l].second;

            int tg ;
            if ( tin[a] <= tin[b] && tout[b] <= tout[a])
                tg = b;
            else
                tg = a ;

            if ( tin[r] < tin[tg] || tout[r] > tout[tg])
            {
                cout << "escaped"<< '\n';
                continue;
            }

            long long ans = cost (r , tg);

            if ( ans >= 1e15 )
            {
                cout << "oo" << '\n';
            }
            else
                cout << ans << '\n' ;


        }
    return 0;
}

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