Submission #1327313

#TimeUsernameProblemLanguageResultExecution timeMemory
1327313ricardsjansonsValley (BOI19_valley)C++20
59 / 100
3089 ms10580 KiB
#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int N=1e5+5;
const ll INF=1e18;

int n,s,q,e,tin[N],tout[N],t=0;
vector<pair<int,int>>adj[N];
pair<int,int>edg[N];
bool shop[N]{};
set<pair<int,int>>unu;

void dfs(int u=e,int p=0){
    tin[u]=t++;
    for(auto[v,c]:adj[u]){
        if(v==p)continue;
        dfs(v,u);
    }
    tout[u]=t++;
}

bool under(int u,int v){
    return tin[v]<=tin[u]&&tout[u]<=tout[v];
}

ll f(int r){
    ll res=INF;
    priority_queue<tuple<ll,int,int>>pq;
    pq.push({0,r,0});
    while(!pq.empty()){
        auto[sum,u,p]=pq.top();
        pq.pop();
        sum*=-1;
        if(shop[u]){
            res=min(res,sum);
            continue;
        }
        for(auto[v,c]:adj[u]){
            if(v==p||unu.count({u,v}))continue;
            pq.push({-sum-c,v,u});
        }
    }
    return res;
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>s>>q>>e;
    for(int i=1;i<=n-1;i++){
        int a,b,w;
        cin>>a>>b>>w;
        adj[a].push_back({b,w});
        adj[b].push_back({a,w});
        edg[i]={a,b};
    }
    for(int i=0;i<s;i++){
        int c;cin>>c;
        shop[c]=1;
    }
    dfs();
    while(q--){
        int i,r;
        cin>>i>>r;
        auto[a,b]=edg[i];
        if(!(under(r,a)&&under(r,b))){
            cout<<"escaped\n";
            continue;
        }
        unu.clear();
        unu.insert({a,b});
        unu.insert({b,a});
        ll res=f(r);
        if(res<INF){
            cout<<res<<"\n";
        }else{
            cout<<"oo\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...