Submission #1106163

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106163		cot7302	Valley (BOI19_valley)	C++17	100 / 100	108 ms	38984 KiB

valley

#include <bits/stdc++.h>
#define ALL(X) begin(X), end(X)
using namespace std;
using i64 = long long;

template <class T>
using vec = vector<T>;

template <class T>
istream& operator>>(istream& is, vec<T>& V) {
    for (auto& x : V) is >> x;
    return is;
}

constexpr int kN = 100'000;

constexpr i64 inf = 4e18, owoovo = 1e18;

int p[__lg(kN) + 1][kN], dep[kN], e_to_v[kN - 1], in[kN], out[kN], dick;

i64 d[__lg(kN) + 1][kN], dp[kN], len[kN];

vec<int> G[kN];

tuple<int, int, int> es[kN - 1];

bitset<kN> eight;

void dfs(int x, int pre) {
    dp[x] = eight[x] ? len[x] : inf;
    in[x] = dick++;
    for (auto ed : G[x]) {
        auto [u, v, w] = es[ed];
        auto to = x ^ u ^ v;
        if (to != pre) {
            p[0][to] = x;
            dep[to] = dep[x] + 1;
            len[to] = len[x] + w;
            e_to_v[ed] = to;
            dfs(to, x);
            dp[x] = min(dp[x], dp[to]);
        }
    }
    out[x] = dick;
    d[0][x] = dp[x] - 2 * len[x];
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, S, q, E; cin >> n >> S >> q >> E;
    E -= 1;
    for (int i = 0; i < n - 1; i++) {
        auto& [u, v, w] = es[i];
        cin >> u >> v >> w;
        u -= 1, v -= 1;
        G[u].emplace_back(i);
        G[v].emplace_back(i);
    }
    for (int i = 0; i < S; i++) {
        int u; cin >> u;
        u -= 1;
        eight[u] = true;
    }
    dfs(E, -1);
    for (int lv = 1, l = __lg(n); lv <= l; lv++) {
        for (int i = 0; i < n; i++) {
            p[lv][i] = p[lv - 1][p[lv - 1][i]];
            d[lv][i] = min(d[lv - 1][i], d[lv - 1][p[lv - 1][i]]);
        }
    }
    while (q--) {
        int e, x; cin >> e >> x;
        e -= 1, x -= 1;
        int u = e_to_v[e];
        if (u == x || (in[u] < in[x] && in[x] < out[u])) {
            int t = dep[x] - dep[u] + 1;
            int y = x;
            i64 ans{inf};
            while (t > 0) {
                int ctz = __builtin_ctz(t);
                ans = min(ans, d[ctz][x]);
                x = p[ctz][x];
                t -= 1 << ctz;
            }
            ans += len[y];
            if (ans < owoovo)
                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