Submission #1368800

#TimeUsernameProblemLanguageResultExecution timeMemory
1368800opeleklanosValley (BOI19_valley)C++20
0 / 100
102 ms87916 KiB
#include <iostream>
#include <vector>
using namespace std;

#define ll long long

#define INF 1000000000000000

vector<pair<ll, ll>> edges;
vector<vector<pair<ll, ll>>> adj;
vector<ll> minDist;
vector<ll> isShop;
vector<pair<ll, ll>> p;
vector<ll> d;

void dfs(ll st, ll par, ll dFromPar, ll depth){
    d[st] = depth;
    p[st] = {par, dFromPar};
    if(isShop[st]) minDist[st] = 0;

    for(auto i : adj[st]){
        if(i.first == par) continue;
        dfs(i.first, st, i.second, depth+1);
        minDist[st] = min(minDist[st], minDist[i.first] + i.second);
    }

}

#define nd first
#define distToNd second.first
#define ans second.second

int main(void){
    // freopen("input.txt", "r", stdin);
    ll N, S, Q, E;
    cin>>N>>S>>Q>>E;
    E--;
    minDist.assign(N, INF);
    adj.assign(N, {});
    isShop.assign(N, 0);
    p.assign(N, {INF, INF});
    d.assign(N, 0);

    for(ll i = 0; i<N-1; i++){
        ll A, B, W;
        cin>>A>>B>>W;
        A--, B--;
        adj[A].push_back({B, W});
        adj[B].push_back({A, W});
        edges.push_back({A, B});
    }

    for(ll i = 0; i<S; i++){
        ll c; cin>>c;
        c--;
        isShop[c] = 1;
    }

    dfs(E, E, 0, 0);

    vector<vector<pair<ll, pair<ll, ll>>>> lift;
    lift.assign(N, vector<pair<ll, pair<ll, ll>>>(30, pair<ll, pair<ll, ll>>{INF, {INF,INF}}));
    for(ll i = 0; i<N; i++){
        lift[i][0] ={p[i].first, {p[i].second, min(minDist[i], minDist[p[i].first] + p[i].second)}};
    }

    for(ll j = 0; j<30; j++){
        for(ll i = 0; i<N; i++){
            auto n = lift[lift[i][j-1].first][j-1];
            lift[i][j] = {n.nd, {lift[i][j-1].distToNd + n.distToNd, 
                min(n.ans + lift[i][j-1].distToNd, lift[i][j-1].ans)}};
        }
    }

    for(ll i = 0; i<Q; i++){
        ll destroyed, st;
        cin>>destroyed>>st;
        destroyed--; st--;

        ll del = edges[destroyed].second;
        if(edges[destroyed].first != p[edges[destroyed].second].first) del = edges[destroyed].first;

        if(isShop[st]) {cout<<0<<endl; continue;}
        if(d[del] > d[st]) {cout<<"escaped"<<endl; continue;}

        ll tmp = st;
        ll mn = minDist[st];
        ll climbed = 0;

        for(ll j = 29; j>=0; j--){
            if((1<<j) & (d[st]-d[del])){
                if(lift[tmp][j].ans<INF) mn = min(mn, lift[tmp][j].ans+climbed);
                climbed += lift[tmp][j].distToNd;
                tmp = lift[tmp][j].nd;
            }
        }

        if(tmp != del) {cout<<"escaped"<<endl; continue;}
        if(mn >= INF) {cout<<"oo"<<endl; continue;}
        cout<<mn<<endl;
    }
}

#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...