Submission #1334093

#TimeUsernameProblemLanguageResultExecution timeMemory
1334093rainmarValley (BOI19_valley)C++20
0 / 100
279 ms42908 KiB
#include<bits/stdc++.h>
using namespace std;

vector<vector<pair<int,int>>> g;
vector<int> in,out;

vector<int> tseen;
vector<int> depth;
vector<int> shop;

vector<long long> dist;
vector<vector<int>> p;

int t = 0;
void dfs(int rn) {
    t++;
    in[rn] = t;
    tseen[rn] = 1;

    for(auto [e,x] : g[rn]) {
        if(tseen[e] == 1) continue;
        p[e][0] = rn;
        depth[e] = depth[rn]+1;
        dist[e] = dist[rn] + x;
        dfs(e);
    }

    out[rn] = t;
}

#define INF 2e15
vector<long long> best;
vector<vector<long long>> jmp;

long long bfs(int rn) {
    long long wow = INF;
    tseen[rn] = 1;

    if(shop[rn] == 1) wow = dist[rn];

    for(auto [a,b] : g[rn]) {
        if(tseen[a] == 1) continue;
        wow = min(wow, bfs(a));
    }

    best[rn] = wow;

    jmp[rn][0] = wow - 2 * dist[rn];
    for(int i = 1; i < 20; i++) {
        p[rn][i] = p[p[rn][i-1]][i-1];
        jmp[rn][i] = min(jmp[rn][i-1], jmp[p[rn][i-1]][i-1]);
    }

    return wow;
}

int main() {

    int N,S,Q,E; cin >> N >> S >> Q >> E;

    E--;

    g.resize(N);
    in = out = vector<int>(N,-1);
    tseen = vector<int>(N,0);
    depth = vector<int>(N,0);
    shop = vector<int>(N,0);
    p = vector<vector<int>>(N, vector<int>(20,E));
    dist = vector<long long>(N,0);

    vector<pair<int,int>> path;

    best = vector<long long>(N,INF);
    jmp = vector<vector<long long>>(N,vector<long long>(20,INF));




    for(int i = 0; i < N-1; i++) {
        int a,b,w; cin >> a >> b >> w;
        a--;
        b--;

        g[a].push_back({b,w});
        g[b].push_back({a,w});

        path.push_back({a,b});
    }

    

    for(int i = 0; i < S; i++) {
        int a; cin >> a;
        a--;
        shop[a] = 1;
    }

    t = 0;
    dfs(E);

    tseen = vector<int>(N,0);
    bfs(E);

    

    for(int q = 0; q < Q; q++) {

        int I,R; cin >> I >> R;
        I--; R--;

        int gh = R;

        int a,b;
        a = path[I].first;
        b = path[I].second;


        if(dist[a] < dist[b]) swap(a,b);

        if(!(in[a] <= in[R] and out[a] >= out[R])) {
            cout << "escape" << "\n";
            continue;
        }

        long long ans = INF;
        for(int j = 19; j >= 0; j--) {
            if(depth[R] - (1 << j) >= depth[a]) {
                ans = min(ans, jmp[R][j]);
                R = p[R][j];
            }
        }

        ans = min(ans, jmp[a][0]);  // include magic[a]

        if(ans > 2e14) {
            cout << "oo\n";
        } else {
            cout << ans + dist[gh] << "\n";
        }

    }


}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...