Submission #1096184

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096184		anarch_y	Valley (BOI19_valley)	C++17	100 / 100	106 ms	52052 KiB

valley

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()
#define pb push_back
#define int long long

const int maxn = 100001;
vector<pair<int, int>> adj[maxn];
int shop[maxn], mnd[maxn], dist[maxn], d[maxn], par[maxn];
int up[maxn][18], up_min[maxn][18];
int tin[maxn], tout[maxn];
int T = 0;

void dfs(int s, int p, int w){
    tin[s] = ++T;
    dist[s] = dist[p] + w;
    d[s] = d[p] + 1;
    if(shop[s]) mnd[s] = 0;
    else mnd[s] = 1e18;
    par[s] = p;
    for(auto [u, ww]: adj[s]){
        if(u == p) continue;
        dfs(u, s, ww);
        mnd[s] = min(mnd[s], mnd[u] + ww);
    }
    tout[s] = T;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, s, q, r;
    cin >> n >> s >> q >> r;
    vector<pair<int, int>> edges(n);
    for(int i=1; i<=n-1; i++){
        int a, b, w; cin >> a >> b >> w;
        adj[a].pb({b, w}); adj[b].pb({a, w});
        edges[i] = {a, b};
    }
    while(s--){
        int x; cin >> x;
        shop[x] = 1;
    }
    dfs(r, 0, 0);
    up[r][0] = r;
    up_min[r][0] = 1e18;
    for(int i=1; i<=n; i++){
        if(i != r){
            up[i][0] = par[i];
            up_min[i][0] = mnd[par[i]] - dist[par[i]];
        } 
    }
    for(int j=1; j<=17; j++){
        for(int i=1; i<=n; i++){
            up[i][j] = up[up[i][j-1]][j-1];
            up_min[i][j] = min(up_min[i][j-1], up_min[up[i][j-1]][j-1]);
        }
    }
    auto jump = [&](int x, int d){
        int ans = 1e18;
        for(int j=17; j>=0; j--){
            if(d & (1<<j)){
                ans = min(ans, up_min[x][j]);
                x = up[x][j];
            } 
        }
        return ans;
    };
    while(q--){
        int i, x; cin >> i >> x;
        auto [a, b] = edges[i];
        if(par[a] == b) swap(a, b);
        if(tin[b] <= tin[x]  and tout[x] <= tout[b]){
            int dd = d[x] - d[b];
            int mn = jump(x, dd);
            int ans = min(mn + dist[x], mnd[x]);
            if(ans != 1e18) cout << ans << "\n";
            else cout << "oo" << "\n";
        }
        else cout << "escaped" << "\n";
    }
}

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