Submission #1328078

#TimeUsernameProblemLanguageResultExecution timeMemory
1328078haryValley (BOI19_valley)C++20
0 / 100
3093 ms24560 KiB
#include <bits/stdc++.h>
#define N 100001
#define INF 1e18
#define LOG 18
#define fi first
#define se second
#define ll long long

using namespace std;

vector<pair<ll,ll>> vec[N];
pair<ll,ll> edg[N];
ll shop[N],weight[N],dist[N],closest[N],in[N],out[N],io=0,par[N][LOG],best[N][LOG],d=0;
//compute dist
//compute par
//compute in/out
//compute closest
void dfs(ll u, ll p){
    closest[u]=(shop[u]? 0:INF);
    in[u]= ++io;
    par[u][0]=p;
    for(ll i=1;i<LOG;i++){
        par[u][i]=par[par[u][i-1]][i-1];

        for(auto dub:vec[u]){
            ll v=dub.fi,w=dub.se;

            if(v!=p){
                dist[v]=dist[u]+w;
                dfs(v,u);
                closest[u]=min(closest[u],closest[v]+w);
            }
        }
    }
    out[u]=io;

}
//compute best paths
void dfs2(ll u, ll p){
    best[u][0]=(dist[u]-dist[p])+closest[p];

    for(ll i=1;i<LOG;i++){
        d=dist[u]-dist[par[u][i-1]];

        best[u][i]=min(best[u][i-1],best[par[u][i-1]][i-1]+d);
    }
    for(auto dub:vec[u]){
        if(dub.fi!=p){
            dfs2(dub.fi,u);
        }
    }
}
bool ispar(ll u, ll v){
    if(in[u]<=in[v]&&out[u]>=out[v]) return 1;
    return 0;
}

ll getbest(ll r, ll u){
    ll cur=closest[r],d=0;

    for(ll i=LOG-1;i>=0;i--){
        ll jump=par[r][i];
        if(!ispar(jump,u)){//cout<<'!';
            cur=min(cur,d+best[r][i]);
            d+=dist[r]-dist[jump];
            r=jump;
        }
    }
    return cur;
}




int main()
{
//ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//fill(closest,closest+N,INF);
//for(ll i=0;i<N;i++)fill(best[i],best[i]+LOG,INF);

ll n=0,s=0,q=0,e=0,a=0,b=0,w=0;
cin>>n>>s>>q>>e;
for(ll i=0;i<n-1;i++){
    cin>>a>>b>>w;
    vec[a].push_back({b,w});
    vec[b].push_back({a,w});
    edg[i]={a,b};
}

for(ll i=0;i<s;i++){
    cin>>a;
    shop[a]=1;
}
dfs(e,e);
dfs2(e,e);

for(ll i=0;i<q;i++){
    cin>>a>>b;
    ll u=edg[a-1].first;
    ll v=edg[a-1].se;
    if(dist[u]<dist[v])swap(u,v);//child node first, parent second

    if(ispar(u,b)){
        ll rez=getbest(b,v);
        if(rez==INF)cout<<"oo\n";
        else cout<<rez<<'\n';
    }
    else cout<<"escaped\n";
}
//for(ll y:in)cout<<y<<' ';
//cout<<'\n';
//for(ll y:out)cout<<y<<' ';
    return 0;
}
//5 2 3 1 1 2 3 1 3 2 3 4 1 3 5 2 2 4 2 2 2 5 4 5
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...