Submission #559984

#TimeUsernameProblemLanguageResultExecution timeMemory
559984abcvuitunggioValley (BOI19_valley)C++17
0 / 100
117 ms92772 KiB
#include <iostream>
#include <vector>
#define int long long
using namespace std;
const int mx=1000000000000000000;
struct edge{
    int u,v,w;
}ed[100001];
int n,s,q,e,st[100001],en[100001],dp[100001],id,c[100001],u,d[100001],p[100001][20],mn[100001][20];
vector <pair <int, int> > ke[100001];
void dfs(int u, int p){
    st[u]=++id;
    if (!c[u])
        dp[u]=mx;
    for (auto v:ke[u])
        if (v.first!=p){
            d[v.first]=d[u]+v.second;
            dfs(v.first,u);
            dp[u]=min(dp[u],dp[v.first]+v.second);
        }
    en[u]=++id;
}
void dfs2(int u, int par){
    for (auto v:ke[u])
        if (v.first!=par){
            p[v.first][0]=u;
            mn[v.first][0]=dp[u];
            dfs2(v.first,u);
        }
}
bool isancestor(int i, int j){
    return (st[i]<=st[j]&&en[i]>=en[j]);
}
void prep(){
    for (int i=1;i<20;i++)
        for (int j=1;j<=n;j++){
            p[i][j]=p[p[i][j-1]][j-1];
            mn[i][j]=min(mn[i][j-1],mn[p[i][j-1]][j-1]);
        }
}
int f(int i, int j){
    int res=dp[i];
    for (int k=19;k>=0;k--)
        if (p[i][k]&&d[p[i][k]]>d[j]){
            res=min(res,mn[i][k]);
            i=p[i][k];
        }
    res=min(res,dp[j]);
    return res;
}
signed main(){
    ios_base::sync_with_stdio(NULL);cin.tie(nullptr);
    cin >> n >> s >> q >> e;
    for (int i=1;i<n;i++){
        cin >> ed[i].u >> ed[i].v >> ed[i].w;
        ke[ed[i].u].push_back({ed[i].v,ed[i].w});
        ke[ed[i].v].push_back({ed[i].u,ed[i].w});
    }
    for (int i=0;i<s;i++){
        cin >> u;
        c[u]=1;
    }
    dfs(e,e);
    for (int i=1;i<=n;i++)
        dp[i]-=d[i];
    dfs2(e,e);
    prep();
    int i,r;
    while (q--){
        cin >> i >> r;
        if (d[ed[i].u]<d[ed[i].v])
            swap(ed[i].u,ed[i].v);
        int u=ed[i].u;
        if (!isancestor(u,r)){
            cout << "escaped\n";
            continue;
        }
        int res=f(r,u)+d[r];
        if (res==mx)
            cout << "oo\n";
        else
            cout << res << '\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...