Submission #1327402

#TimeUsernameProblemLanguageResultExecution timeMemory
1327402ricardsjansonsValley (BOI19_valley)C++20
100 / 100
101 ms34088 KiB
#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int N=1e5+5,K=17;
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]{};
int par[N][K]{};
ll dis[N]{},lift[N][K];

ll dfs(int u=e,int p=0){
    tin[u]=t++;
    par[u][0]=p;
    ll csd=(shop[u]?0:INF);
    for(auto[v,c]:adj[u]){
        if(v==p)continue;
        dis[v]=dis[u]+c;
        csd=min(csd,dfs(v,u)+c);
    }
    lift[u][0]=csd-dis[u];
    tout[u]=t++;
    return csd;
}

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

ll f(int a,int b){
    //cout<<a<<" "<<b<<"\n";
    ll res=lift[b][0];
    int u=b;
    for(int i=K-1;i>=0;i--){
        int v=par[u][i];
        if(!v||dis[v]<dis[a])continue;
        //cout<<"!"<<v<<"\n";
        res=min(res,lift[par[u][0]][i]);
        u=v;
    }
    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();
    lift[0][0]=INF;
    for(int i=1;i<K;i++){
        for(int u=1;u<=n;u++){
            int v=par[u][i-1];
            par[u][i]=par[v][i-1];
        }
    }
    for(int i=1;i<K;i++){
        for(int u=1;u<=n;u++){
            int v=par[u][i-1];
            lift[u][i]=min(lift[u][i-1],lift[v][i-1]);
        }
    }
    while(q--){
        int i,r;
        cin>>i>>r;
        auto[a,b]=edg[i];
        if(!(under(r,a)&&under(r,b))){
            cout<<"escaped\n";
            continue;
        }
        ll res=f((dis[a]>dis[b]?a:b),r);
        if(res<INF/100){
            cout<<res+dis[r]<<"\n";
        }else{
            cout<<"oo\n";
        }
    }
    for(int i=0;i<K;i++){
        //cout<<lift[5][i]<<"\n";
    }
    //cout<<dis[3];
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...