Submission #1327362

#TimeUsernameProblemLanguageResultExecution timeMemory
1327362edga1Valley (BOI19_valley)C++20
23 / 100
128 ms64316 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 tin[N], tout[N];
ll mi[N][20],d[N][20],pa[N][20];
ll cd[N];
ll S[N];
ll top,t=0;

void dfs(ll v, ll p, ll dpre){
    cd[v]=INF;
    if(S[v]) cd[v]=0;
    tin[v]=t;
    t++;
    d[v][0]=dpre;
    pa[v][0]=p;
    mi[v][0]=cd[p]+dpre;
    for(ll i=1; i<20; i++){
        pa[v][i]=pa[pa[v][i-1]][i-1];
        d[v][i]=d[v][i-1]+d[pa[v][i-1]][i-1];
        mi[v][i]=min(mi[v][i-1],d[v][i-1]+mi[pa[v][i-1]][i-1]);
    }
    for(auto u : g[v]){
        if(u.fi==p) continue;
        dfs(u.fi,v,u.se);
        cd[v]=min(cd[v],cd[u.fi]+u.se);
    }
    tout[v]=t;
    t++;
}

ll virs(ll a, ll b){
    return (tin[a]<tin[b] && tout[a]>tout[b]);
}

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;
    }
    dfs(top,top,0);
    for(ll i=0; i<q; i++){
        ll ban,r;
        cin>>ban>>r;
        ll a=roads[ban-1].fi,b=roads[ban-1].se;
        if(virs(b,a)) swap(b,a);
        if(tin[a]<tin[r] && tout[a]>tout[r] && tout[b]>=tout[r] && tin[b]<=tin[r]){
            ll atb=cd[r];
            ll l=20;
            while(l>0){
                l--;
                ll nr=pa[r][l];
                if(virs(nr,b)) continue;
                atb=min(atb,mi[r][l]);
                r=nr;
            }
            if(atb==INF) cout<<"oo\n";
            else cout<<atb<<'\n';
        }
        else cout<<"escaped\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...