Submission #1042336

#	Time	Username	Problem	Language	Result	Execution time	Memory
1042336		Thunnus	Valley (BOI19_valley)	C++17	100 / 100	157 ms	56576 KiB

valley

#include <bits/stdc++.h>

using namespace std;
using i64 = long long;

const int N = 100000;
const i64 inf = 1e18;
int n, s, q, E, t = 0;

vector<i64> in(N), out(N), shop(N), x(N, inf), dp(N), d(N);
vector<pair<int, int>> e;
vector<vector<pair<int, int>>> g(N);
vector<vector<i64>> go(N, vector<i64>(18)), mn(N, vector<i64>(18));

void dfs(int u, int p) {
    in[u] = t++;
    go[u][0] = p;
    if (shop[u]) {
        x[u] = d[u];
    }
    for (auto [v, w] : g[u])  { 
        if (v != p) {
            d[v] = d[u] + w;
            dfs(v, u);
            x[u] = min(x[u], x[v]);
        }
    }
    dp[u] = (x[u] == inf ? inf : x[u] - 2 * d[u]);
    mn[u][0] = dp[u];
    out[u] = t++;
}

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> n >> s >> q >> E;
    --E;

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

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

    dfs(E, E);

    for (int b = 1; b < 18; b++) {
        for (int i = 0; i < n; i++) {
            go[i][b] = go[go[i][b - 1]][b - 1];
            mn[i][b] = min(mn[i][b - 1], mn[go[i][b - 1]][b - 1]);
        }
    }

    while (q--) {
        int i, r;
        cin >> i >> r;
        --i; --r;
        auto [u, v] = e[i];
        if (is_ancestor(u, v)) {
            swap(u, v);
        }
        if (!is_ancestor(u, r)) {
            cout << "escaped\n";
        } else {
            i64 best = dp[u], dd = d[r];
            for (int b = 17; b >= 0; b--) {
                if (is_ancestor(u, go[r][b])) {
                    best = min(best, mn[r][b]);
                    r = go[r][b];
                }
            }
            if (best == inf) {
                cout << "oo\n";
            } else {
                cout << dd + best << '\n';
            }
        }
    }
}

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