Submission #1347578

#TimeUsernameProblemLanguageResultExecution timeMemory
1347578Godgift42Valley (BOI19_valley)C++20
0 / 100
193 ms40816 KiB
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct edge{
    int a,b;
    ll w;
};

const ll inf=1000000000000000000;

vector<vector<pair<int,ll>>> adj;
int l;
vector<vector<int>> up;
vector<ll> ma;
vector<vector<ll>> mup;
vector<int> tin;
vector<ll> dpt;
vector<int> tout;
int timer=-1;
vector<int> iss;

void ini(int u, int p){
    timer++;
    tin[u]=timer;
    up[u][0]=p;
    for(int i=1;i<=l;i++)up[u][i]=up[up[u][i-1]][i-1];
    if(iss[u])ma[u]=0;
    else ma[u]=inf;
    for(auto [v,w]: adj[u]){
        if(v!=p){
            dpt[v]=dpt[u]+w;
            ini(v,u);
            ma[u]=min(ma[u],ma[v]+w);
        }
    }
    mup[u][0]=min(ma[p]+dpt[u]-dpt[p],inf);
    for(int i=1;i<=l;i++){
        mup[u][i]=min(mup[u][i-1],mup[up[u][i-1]][i-1]+dpt[u]-dpt[up[u][i-1]]);
    }
    timer++;
    tout[u]=timer;
}

bool isanc(int u, int v){
    if(tin[u]<=tin[v] and tout[u]>=tout[v])return true;
    return false;
}

int lca(int u, int v){
    if(isanc(u,v))return u;
    if(isanc(v,u))return v;
    for(int i=l;i>=0;i--){
        if(!isanc(up[u][i],v))u=up[u][i];
    }
    return up[u][0];
}

int main(){
    int n,s,q,e;
    cin >> n >> s >> q >> e;
    e--;
    l=ceil(log2(n));
    adj.resize(n);
    iss.resize(n);
    tin.resize(n);
    tout.resize(n);
    ma.resize(n);
    up.resize(n,vector<int>(l+1));
    mup.resize(n,vector<ll>(l+1));
    vector<edge> edl;
    dpt.resize(n);
    for(int i=0;i<n-1;i++){
        edge c;
        cin >> c.a >> c.b >> c.w;
        c.a--;
        c.b--;
        adj[c.a].push_back({c.b,c.w});
        adj[c.b].push_back({c.a,c.w});
        edl.push_back(c);
    }
    for(int i=0;i<s;i++){
        int x;
        cin >> x;
        x--;
        iss[x]=1;
    }
    ini(e,e);
    while(q--){
        int id,u;
        cin >> id >> u;
        id--;u--;
        int rt1=lca(edl[id].a,u);
        int rt2=lca(edl[id].b,u);
        if(rt1==edl[id].a and rt2==edl[id].b){
            if(dpt[rt1]<dpt[rt2])rt1=rt2;
            ll ans=ma[u];
            int cu=u;
            for(int i=l;i>=0;i--){
                if(isanc(rt1,up[cu][i])){
                    ans=min(ans,mup[cu][i]);
                    cu=up[cu][i];
                }
            }
            if(ans!=inf)cout << ans << "\n";
            else cout << "oo\n";
        }
        else cout << "escape\n";
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...