제출 #1348425

#제출 시각아이디문제언어결과실행 시간메모리
1348425Born_To_LaughValley (BOI19_valley)C++17
100 / 100
101 ms46908 KiB
// Born_To_Laugh - Hughie Do
#include <bits/stdc++.h>
#define alle(AC) AC.begin(), AC.end()
#define fi first
#define se second
using namespace std;
typedef long long ll;
[[maybe_unused]] const ll MOD = 998244353, INF = 3e18 + 7;

const int maxn = 1e5 + 10;
int n, q, s, e, id = 0;
vector<pair<int, int>> adj[maxn];
int isC[maxn];
int tin[maxn], tout[maxn];

ll binlift[maxn][20], qr[maxn][20];
ll dp[maxn], dep[maxn];
ll val[maxn];

pair<pair<int, int>, int> edge[maxn];

void dfs(int a, int par){
    tin[a] = ++id;
    if(isC[a]) dp[a] = 0;
    else dp[a] = INF;
    for(auto &elm: adj[a]){
        if(elm.fi == par) continue;
        dep[elm.fi] = dep[a] + elm.se;
        dfs(elm.fi, a);
        dp[a] = min(dp[a], dp[elm.fi] + elm.se);
    }
    tout[a] = id;
}
void dfsbl(int a, int par){
    for(auto &elm: adj[a]){
        int x = elm.fi, w = elm.se;
        if(x == par) continue;
        binlift[x][0] = a;
        qr[x][0] = dp[a] - dep[a];
        for(int i=1; i<20; ++i){
            binlift[x][i] = binlift[binlift[x][i - 1]][i - 1];
            qr[x][i] = min(qr[x][i - 1], qr[binlift[x][i - 1]][i - 1]);
        }
        dfsbl(x, a);
    }
}
void solve(){
    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});
        edge[i] = {{a, b}, c};
    }
    for(int i=1; i<=s; ++i){
        int x;cin >> x;
        isC[x] = 1;
    }
    dfs(e, -1);
    dfsbl(e, -1);
    while(q--){
        int lon, r;cin >> lon >> r;
        int a = edge[lon].fi.fi, b = edge[lon].fi.se;
        if(dep[a] > dep[b]) swap(a, b);
        if(tin[b] <= tin[r] && tin[r] <= tout[b]){
            int x = r;
            ll ans = dp[r];
            for(int i=19; i>=0; --i){
                if(dep[binlift[x][i]] >= dep[b]){
                    ans = min(ans, dep[r] + qr[x][i]);
                    x = binlift[x][i];
                }
            }
            if(ans >= INF){
                cout << "oo\n";
            }
            else cout << ans << '\n';
        }
        else{
            cout << "escaped\n";
        }
    }
}
signed main(){
    // freopen("inp.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    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...