Submission #1060433

#	Time	Username	Problem	Language	Result	Execution time	Memory
1060433		BF001	Valley (BOI19_valley)	C++17	100 / 100	90 ms	48980 KiB

valley

#include<bits/stdc++.h>
using namespace std;
 
#define N 100005
#define int long long
#define log 16
#define oo 1e18
#define fi first
#define se second

typedef pair<int, int> ii;
 
int par[log + 2][N], mi[log + 2][N], dp[N], q, dep[N], tin[N], tout[N], tim, n, root, m, dis[N];
vector<ii> adj[N];
ii eg[N];

void dfs(int u, int p){
    tin[u] = ++tim;
    for (auto x : adj[u]){
        int v = x.fi, w = x.se;
        if (v == p) continue;
        dep[v] = dep[u] + 1;
        dis[v] = dis[u] + w;
        dfs(v, u);
        dp[u] = min(dp[u], dp[v] + w);
        par[0][v] = u;
    }
    if (dp[u] != oo) mi[0][u] = dp[u] -  dis[u];
    tout[u] = tim;
}

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

int go(int u, int len){
    int rt = oo;
    for (int k = log; k >= 0; k--){
        if ((1 << k) <= len){
            len -= (1 << k);
            rt = min(rt, mi[k][u]);
            u = par[k][u];
        }
    }
    return rt;
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    
    cin >> n >> m >> q >> root;
    for (int i = 1; i <= n - 1; i++){
        int u, v, w;
        cin >> u >> v >> w;
        eg[i] = {u, v};
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    for (int i = 1; i <= n; i++){
        mi[0][i] = oo;
        dp[i] = oo;
    }

    for (int i = 1; i <= m; i++){
        int val;
        cin >> val;
        dp[val] = 0;
    }

    dfs(root, 0);
    for (int k = 1; k <= log; k++){
        for (int i = 1; i <= n; i++){
            par[k][i] = par[k - 1][par[k - 1][i]];
            mi[k][i] = min(mi[k - 1][i], mi[k - 1][par[k - 1][i]]);
        }
    }

    while (q--){
        int i, r;
        cin >> i >> r;
        if (dep[eg[i].fi] > dep[eg[i].se]) swap(eg[i].fi, eg[i].se);
        if (!in(eg[i].se, r)){
            cout << "escaped\n";
            continue;
        }
        int res = dis[r] + go(r, dep[r] - dep[eg[i].se] + 1);
        if (res >= oo){
            cout << "oo\n";
        }
        else cout << res << "\n";
    }

    return 0;
}

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