Submission #922718

#	Time	Username	Problem	Language	Result	Execution time	Memory
922718		Alihan_8	Valley (BOI19_valley)	C++17	100 / 100	286 ms	65940 KiB

valley

#include <bits/stdc++.h>

using namespace std;

#define all(x) x.begin(), x.end()
#define ar array
#define pb push_back
#define ln '\n'
#define int long long

using i64 = long long;

template <class F, class _S>
bool chmin(F &u, const _S &v){
    bool flag = false;
    if ( u > v ){
        u = v; flag |= true;
    }
    return flag;
}

template <class F, class _S>
bool chmax(F &u, const _S &v){
    bool flag = false;
    if ( u < v ){
        u = v; flag |= true;
    }
    return flag;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, s, q, rt;
    cin >> n >> s >> q >> rt;
    --rt;

    vector <vector<ar<int,3>>> G(n);

    for ( int i = 0; i + 1 < n; i++ ){
        int u, v, w; cin >> u >> v >> w;
        --u, --v;
        G[u].pb({v, w, i});
        G[v].pb({u, w, i});
    }

    const int inf = 1e18;

    vector <int> dp(n, inf);

    for ( int i = 0; i < s; i++ ){
        int u; cin >> u;
        dp[--u] = 0;
    }

    vector <ar<int,2>> tree(n - 1);

    vector <vector<int>> up(n, vector <int> (20, rt)), val(n, vector <int> (20, inf));

    vector <int> tin(n), tout(n), d(n);

    int ct = 0;

    auto Dp = [&](auto Dp, int u, int p) -> void{
        for ( auto &[v, w, i]: G[u] ){
            if ( v != p ){
                Dp(Dp, v, u);
                chmin(dp[u], dp[v] + w);
            }
        }
    };

    Dp(Dp, rt, rt);

    auto dfs = [&](auto dfs, int u, int p) -> void{
        tin[u] = ++ct;
        up[u][0] = p;
        val[u][0] = dp[u] - d[u];
        for ( int i = 1; i < 20; i++ ){
            up[u][i] = up[up[u][i - 1]][i - 1];
            val[u][i] = min(val[u][i - 1], val[up[u][i - 1]][i - 1]);
        }
        for ( auto &[v, w, i]: G[u] ){
            if ( v != p ){
                tree[i] = {u, v};
                d[v] = d[u] + w;
                dfs(dfs, v, u);
            }
        } tout[u] = ct;
    };

    dfs(dfs, rt, rt);

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

    while ( q-- ){
        int i, r; cin >> i >> r;
        --i, --r;
        if ( !isAnc(tree[i][1], r) ){
            cout << "escaped\n";
            continue;
        }
        int opt = dp[r], u = r, v = tree[i][1], c = d[r];
        for ( int j = 19; j >= 0; j-- ){
            if ( d[up[r][j]] >= d[v] ){
                chmin(opt, val[r][j] + c);
                r = up[r][j];
            }
        }
        chmin(opt, dp[v] - d[v] + d[u]);
        if ( opt >= 1e16 ){
            cout << "oo\n";
        } else cout << opt << ln;
    }

    cout << '\n';
}

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