제출 #1314865

#제출 시각아이디문제언어결과실행 시간메모리
1314865hssaan_arifValley (BOI19_valley)C++20
23 / 100
158 ms48888 KiB
// #include <bits/stdc++.h>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <vector>
#include <iomanip>
#include <string>
#include <queue>
#include <set>
#include <deque>
using namespace std;

#define endl "\n"
#define pb push_back
#define int long long
#define fi first
#define se second

const int N = 3e5 + 5, M = 1e9 + 7, LG = 20;

int n , A[N] , u , v , w , q , e , s , x , P[N] , dp[N] , I[N] , in = 1 , U[N] , V[N] , O[N] , sp[N][LG] , dep[N] , pr[N][LG];
bool vi[N];
vector<pair<int,int>> lis[N];

void dfs(int v , int par , int wi){
    P[v] = par;
    dp[v] = 1e18;
    dep[v] = dep[par] + wi;
    I[v] = in;
    in++;
    
    for (auto [u,w] : lis[v]){
        if (u == par) continue;
        dfs(u , v , w);
        dp[v] = min(dp[v] , dp[u]);
    }

    if (vi[v]){
        dp[v] = dep[v];
    }

    sp[v][0] = dp[v] - 2 * dep[v];
    pr[v][0] = par;
    O[v] = in;
    in++;

}

void solve(){
    cin >> n >> s >> q >> e;

    dp[0] = 1e18;

    for (int i=1 ; i<n ; i++){
        cin >> u >> v >> w;

        lis[u].pb({v,w});
        lis[v].pb({u,w});
        U[i] = u;
        V[i] = v;
    }

    for (int i=1 ; i<=s ; i++){
        cin >> x;
        vi[x] = 1;
    }

    dfs(e , 0 , 0);

    for (int j=1 ; j<LG ; j++){
        for (int i=1 ; i<=n ; i++){
            pr[i][j] = pr[pr[i][j-1]][j-1];
        }
    }

    for (int j=1 ; j<LG ; j++){
        for (int i=1 ; i<=n ; i++){
            if (!pr[i][j]) continue;
            sp[i][j] = min(sp[i][j-1] , sp[pr[i][j-1]][j-1]);
        }
    }

    while(q--){
        cin >> x >> v;
        int u = -1;

        if (P[U[x]] == V[x]){
            u = U[x];
        }else{
            u = V[x];
        }

        if (I[v] >= I[u] && O[v] <= O[u]){
            int ans = dp[v] - 2 * dep[v] , v1 = v;

            for (int i=LG-1 ; i>=0 ; i--){
                if (!pr[v][i]) continue;

                int j = pr[v][i];

                if (I[j] >= I[u] && O[j] <= O[u]){
                    v = pr[v][i];
                    ans = min(ans , sp[v][i]);
                }

            }

            ans += dep[v1];
            // cout << sp[5][1] << endl;

            if (ans >= 1e15){
                cout << "oo" << endl;
            }else{
                cout << ans << endl;
            }
        }else{
            cout << "escaped" << endl;
        }
        
    }
}

signed main(){
    // freopen("" , "r" , stdin);
    // freopen("" , "w" , stdout);
    // cout << setprecision(30);
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int ts = 1;
    // cin >> ts;
    while(ts--){
        solve();
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...