Submission #1327305

#TimeUsernameProblemLanguageResultExecution timeMemory
1327305edga1Valley (BOI19_valley)C++20
36 / 100
3093 ms10440 KiB
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back

using namespace std;

const ll N=1e5+5;
const ll INF=1e18;
vector<pair<ll,ll>> g[N];
vector<pair<ll,ll>> roads;
ll S[N];
ll ns,e,top;

void dfs(ll v, ll p, ll d, ll ban){
    if(v==top) e=1;
    if(S[v]) ns=min(ns,d);
    pair<ll,ll> ro=roads[ban];
    ll a=ro.fi,b=ro.se;
    for(auto u : g[v]){
        if(u.fi==p) continue;
        if((u.fi==a && v==b) || (u.fi==b && v==a)) continue;
        dfs(u.fi,v,d+u.se,ban);
    }
    return;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    ll n,s,q;
    cin>>n>>s>>q>>top;
    for(ll i=0; i<n-1; i++){
        ll a,b,w;
        cin>>a>>b>>w;
        g[a].pb({b,w});
        g[b].pb({a,w});
        roads.pb({a,b});
    }
    for(ll i=0; i<s; i++){
        ll a; cin>>a;
        S[a]=1;
    }
    for(ll i=0; i<q; i++){
        ll ban,r;
        cin>>ban>>r;
        e=0;
        ns=INF;
        dfs(r,r,0,ban-1);
        if(e) cout<<"escaped\n";
        else if(ns!=INF) cout<<ns<<'\n';
        else cout<<"oo\n";
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...