Submission #896137

#	Time	Username	Problem	Language	Result	Execution time	Memory
896137		box	Valley (BOI19_valley)	C++17	100 / 100	153 ms	44884 KiB

valley

#include <bits/stdc++.h>
using namespace std;

#define ar array
#define all(v) begin(v), end(v)
#define sz(v) int(std::size(v))
using i64 = long long;
using pii = pair<int, int>;
using vi = vector<int>;

const i64 INF = 1e18;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, S, Q, E;
    cin >> N >> S >> Q >> E, E--;
    vector<vector<pii>> adj(N);
    vector<pii> edges(N - 1);
    for (auto &[i, j] : edges) {
        int w; cin >> i >> j >> w, i--, j--;
        adj[i].push_back({j, w}), adj[j].push_back({i, w});
    }
    vi is_shop(N);
    while (S--) {
        int i; cin >> i, i--;
        is_shop[i] = 1;
    }
    const int LOG = 17;
    vector<ar<int, LOG>> parent(N);
    vector<ar<i64, LOG>> min_v(N);
    vi tin(N), tout(N), depth(N);
    vector<i64> dist_root(N);
    int timer = 0;
    vector<i64> dist(N);
    auto dfs = [&](auto dfs, int p, int i) -> void {
        dist[i] = is_shop[i] ? 0 : INF;
        tin[i] = timer++;
        parent[i][0] = p;
        for (int l = 1; l < LOG; l++) parent[i][l] = parent[parent[i][l - 1]][l - 1];
        for (auto [j, w] : adj[i]) if (p != j) {
            depth[j] = depth[i] + 1;
            dist_root[j] = dist_root[i] + w;
            dfs(dfs, i, j);
            dist[i] = min(dist[i], dist[j] + w);
        }
        tout[i] = timer - 1;
    };
    dfs(dfs, E, E);
    auto make_v = [&](auto make_v, int i) -> void {
        min_v[i][0] = dist[i] - dist_root[i];
        for (int l = 1; l < LOG; l++) min_v[i][l] = min(min_v[i][l - 1], min_v[parent[i][l - 1]][l - 1]);
        for (auto [j, w] : adj[i]) if (parent[i][0] != j) make_v(make_v, j);
    };
    make_v(make_v, E);
    vi lower(N - 1);
    for (int i = 0; i < sz(edges); i++)
        lower[i] = tin[edges[i].first] < tin[edges[i].second] ? edges[i].second : edges[i].first;
    auto is_anc = [&](int i, int j) {
        return tin[i] <= tin[j] && tout[i] >= tout[j];
    };
    while (Q--) {
        int h, i; cin >> h >> i, h--, i--;
        int j = lower[h];
        if (!is_anc(j, i)) {
            cout << "escaped\n";
            continue;
        }
        int d = depth[i] - depth[j] + 1, v = i;
        i64 best = INF;
        for (int l = 0; l < LOG; l++) if (d >> l & 1) {
            best = min(best, min_v[v][l]);
            v = parent[v][l];
        }
        best += dist_root[i];
        if (best > INF / 2) {
            cout << "oo\n";
            continue;
        }
        cout << best << '\n';
    }
}

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