제출 #1299711

#제출 시각아이디문제언어결과실행 시간메모리
1299711erfang1382Valley (BOI19_valley)C++20
100 / 100
278 ms50036 KiB
#include <bits/stdc++.h>

using namespace std;
 
#define ll long long
#define ld long double 
#define lll __ll128
#define sza(x) ((ll)x.size())
#define all(a) (a).begin(), (a).end()
#define pb push_back
#define pll pair<ll,ll>
 

#ifdef DEBUG
    #include "helper.h"
#else
    #define dbg(...)
#endif

#define log(a) 63-__builtin_clzll(a)

const ll INF=1e18;
const ll MOD=1e9+7;


void solve() {
    int n,s,q,e;

    cin>>n>>s>>q>>e;
    e--;


    vector<vector<pair<int,ll>>> edges(n);
    vector<pair<int,int>> all_edges;
    set<int> shops;
    for(int i=0;i<n-1;i++){
        int a,b;
        ll c;
        cin>>a>>b>>c;
        a--,b--;
        all_edges.push_back({a,b});
        edges[a].push_back({b,c});
        edges[b].push_back({a,c});
    }

    for(int i=0;i<s;i++){
        int a;
        cin>>a;
        a--;
        shops.insert(a);
    }

    int LOG=__lg(n);

    vector<vector<pair<int,ll>>> bj(n,vector<pair<int,ll>>(LOG+1,{-1,LLONG_MAX}));
    vector<int> depth(n);
    vector<ll> cost(n);
    vector<ll> dp(n,LLONG_MAX);
    dbg(dp);
    
    dbg(edges);
    auto build=[&](auto && build, int u,int p,int _depth,ll _cost ) -> void {
        cost[u]=_cost;
        depth[u]=_depth;
        bj[u][0].first=p;
        if(shops.contains(u)){
            dp[u]=0;
        }
        // dbg(u,p);
        for(auto nei:edges[u]){
            if(nei.first==p)continue;
            build(build,nei.first,u,_depth+1,_cost+nei.second);
            if(dp[nei.first]!=LLONG_MAX)
                dp[u]=min(dp[u],nei.second+dp[nei.first]);
        }

    };
    build(build,e,-1,0,0);
    dbg(1);
    for(int i=0;i<n;i++){
        bj[i][0].second=min(-cost[bj[i][0].first]+dp[bj[i][0].first],-cost[i]+dp[i]);
    }

    for(int log=1;log<=LOG;log++){
        for(int i=0;i<n;i++){
            auto [v,cost]=bj[i][log-1];

            if(v!=-1){
                bj[i][log].first=bj[v][log-1].first;
                bj[i][log].second=min(bj[v][log-1].second,bj[i][log-1].second);
            }
        }
    }



    auto get_ans=[&](int  v,int num) -> pair<int,ll> {
        int curr=v;
        ll curr_cost=-cost[v]+dp[v];


        for(int i=0;i<=LOG;i++){
            if(num&(1<<i)){
                curr_cost=min(curr_cost,bj[curr][i].second);
                curr=bj[curr][i].first;
            }
            if(curr==-1)return {-1,LLONG_MAX};;
        }

        return {curr,curr_cost+cost[v]};
    };

    while(q--){
        int index;
        int v;
        cin>>index>>v;
        index--,v--;
        auto [_p,_q]=all_edges[index];
        dbg(v);
        if(depth[_q]<depth[_p])swap(_p,_q);
        dbg(get_ans(v,-depth[_q]+depth[v]),depth[_q]-depth[v]);
        if(get_ans(v,-depth[_q]+depth[v]).first!=_q){
            cout<<"escaped"<<endl;
        }else{
            auto [_v,ans]=get_ans(v,-depth[_q]+depth[v]);
            if(ans==LLONG_MAX){
                cout<<"oo"<<endl;
            }else{
                cout<<ans<<endl;

            }
        }
    }



}
 
 
int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("cbarn2.in","r",stdin);
    // freopen("cbarn2.out","w",stdout);
    // cout<<1<<endl;
 
    // dbg(deals);
 
    // ll t;
    // cin>>t;
    // while(t--)
    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...