Submission #559995

#	Time	Username	Problem	Language	Result	Execution time	Memory
559995		abcvuitunggio	Valley (BOI19_valley)	C++17	100 / 100	231 ms	54348 KiB

valley

#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[j][i]=p[p[j][i-1]][i-1];
            mn[j][i]=min(mn[j][i-1],mn[p[j][i-1]][i-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++)
        if (dp[i]!=mx)
            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);
        if (res==mx)
            cout << "oo\n";
        else
            cout << res+d[r] << '\n';
    }
}

• Subtask 1: 9 / 9
• Subtask 2: 27 / 27
• Subtask 3: 23 / 23
• Subtask 4: 41 / 41