제출 #1360737

#제출 시각아이디문제언어결과실행 시간메모리
1360737ChocoValley (BOI19_valley)C++20
23 / 100
2916 ms73992 KiB
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
#define ll  long long 
#define fori(i,j,k) for(ll i=j; i<=k;i++)
#define study ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define pb push_back
#define all(s) s.begin(),s.end()
#define ins insert
#define ss second
#define ff first
const ll sz=1e5+10;
ll INF=1e18;
ll mod=1e9+7;
ll limit=1e15;
ll tame=0;
vector<vector<pair<ll,ll>>>adj(sz);
vector<vector<ll>>lca(sz,vector<ll>(30,-1)),mini(sz,vector<ll>(30,-1));
vector<ll>in(sz,0),out(sz,0),dp(sz,INF),shops,depth(sz,0);
void restart(ll n){
    adj.clear();
    in.clear();
    out.clear();
    adj.assign(n+10,{});
    in.assign(n+10,0); out.assign(n+10,0);
    tame=0;
}
void dfs(ll t,ll par=-1,ll dap=0){
    tame++;
    in[t]=tame;
    depth[t]=dap;
    lca[t][0]=par;
    if(count(all(shops),t))
    dp[t]=depth[t];
    for(auto x: adj[t]){
        if(x.ff==par)
        continue;
        dfs(x.ff,t,dap+x.ss);
        dp[t]=min(dp[t],dp[x.ff]);
    }
    mini[t][0]=dp[t]-2*depth[t];
    out[t]=tame;
}
void lcs(ll n){
    fori(i,1,29){
        fori(j,1,n){
            if(lca[j][i-1]==-1)
            continue;
            lca[j][i]=lca[lca[j][i-1]][i-1];
        }
    }
    fori(i,1,29){
        fori(j,1,n){
            if(lca[j][i-1]==-1)
            continue;
            mini[j][i]=min(mini[j][i-1],mini[lca[j][i-1]][i-1]);
        }
    }
}
void work(){
    ll n,m,q,st;
    cin>>n>>m>>q>>st;
    vector<pair<ll,ll>>ro(n+10);
    fori(i,1,n-1){
        ll a,b,wei;
        cin>>a>>b>>wei;
        ro[i]={a,b};
        adj[a].pb({b,wei});
        adj[b].pb({a,wei});
    }
    fori(i,1,m){
        ll x;
        cin>>x;
        shops.pb(x);
    }
    dfs(st,-1,0);
    lcs(n);
    fori(rando,1,q){
        ll ind, qu;
        cin>>ind>>qu;
        ll a=ro[ind].ff,b=ro[ind].ss;
        if(in[a]<=in[qu] and out[a]>=out[qu] and in[b]<=in[qu] and out[b]>=out[qu]){
            ll last=a;
            if(in[a]<=in[b]){
                last=b;
            }
            if(count(all(shops),qu)){
                cout<<0<<endl;
                continue;
            }
            ll oar=qu;
            ll ans=mini[qu][0];
            fori(i,0,29){
                if(lca[qu][i]==-1)
                continue;
                if(in[lca[qu][i]]>=in[last]){
                    ans=min(ans,mini[qu][i]);
                    qu=lca[qu][i];
                }
            }
            ans=min(ans,mini[qu][0]);
            ans+=depth[oar];
            if(ans>=limit)
            cout<<"oo"<<endl;
            else
            cout<<ans<<endl;
        }
        else{
            cout<<"escaped\n";
        }
    }
}
int main()
{
    // #ifndef LOCAL
    // freopen("snowcow.in","r",stdin);
    // freopen("snowcow.out","w",stdout);
    // #endif
    study;
    ll t=1;
    //cin>>t;
    fori(i,1,t){
    work();
    }
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…