Submission #1368768

#TimeUsernameProblemLanguageResultExecution timeMemory
1368768opeleklanosValley (BOI19_valley)C++20
0 / 100
192 ms47948 KiB
#include <iostream>
#include <vector>
using namespace std;

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

int t = 0;
void dfs(int st, int par, int dFromPar, int depth){
    d[st] = depth;
    p[st] = {par, dFromPar};
    if(isShop[st]) minDist[st] = 0;
    t++;
    for(auto i : adj[st]){
        if(i.first == par) continue;
        dfs(i.first, st, i.second, depth+1);
        if(minDist[st] == -1 && minDist[i.first]!=-1) minDist[st] = i.second + minDist[i.first];
        if(minDist[i.first] != -1) minDist[st] = min(minDist[st], i.second + minDist[i.first]);
    }
    t++;
}

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

    for(int i = 0; i<N-1; i++){
        int 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(int i = 0; i<S; i++){
        int c; cin>>c;
        c--;
        isShop[c] = 1;
    }

    dfs(E, E, 0, 0);

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

    for(int j = 1; j<30; j++){
        for(int i = 0; i<N; i++){
            auto n = lift[lift[i][j-1].first][j-1];
            lift[i][j] = {n.first, {lift[i][j-1].second.first + n.second.first, 
                min(n.second.second + lift[i][j-1].second.first, lift[i][j-1].second.second)}};
            
            if(n.second.second == -1 && lift[i][j-1].second.second == -1) lift[i][j].second.second = -1;
            if(n.second.second == -1) lift[i][j].second.second = lift[i][j-1].second.second;
            if(lift[i][j-1].second.second == -1) lift[i][j].second.second = n.second.second + lift[i][j-1].second.first;
        }
    }

    for(int i = 0; i<Q; i++){
        int destroyed, st;
        cin>>destroyed>>st;
        destroyed--; st--;
        int 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;}

        int tmp = st;
        int mn = 2000000000;
        int climbed = 0;
        for(int j = 29; j>=0; j--){
            if((1<<j) & (d[st]-d[del])){
                climbed += lift[tmp][j].second.first;
                tmp = lift[tmp][j].first;
                if(lift[tmp][j].second.second!=-1) mn = min(mn, lift[tmp][j].second.second+climbed);
            }
        }

        if(tmp != del) {cout<<"escaped"<<endl; continue;}
        if(mn == 2000000000) {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...