Submission #396928

#	Time	Username	Problem	Language	Result	Execution time	Memory
396928		KoD	Valley (BOI19_valley)	C++17	100 / 100	501 ms	43024 KiB

valley

#include <bits/stdc++.h>

template <class T>
using Vec = std::vector<T>;

using ll = long long;

template <class F>
struct RecLambda: private F {
    RecLambda(F&& f): F(std::forward<F>(f)) { }
    template <class... Args>
    decltype(auto) operator () (Args&&... args) const {
        return F::operator()(*this, std::forward<Args>(args)...);
    }
};

constexpr ll INF = std::numeric_limits<ll>::max() / 2;

int main() {
    int N, S, Q, E;
    std::cin >> N >> S >> Q >> E;
    E -= 1;
    Vec<int> A(N - 1), B(N - 1), W(N - 1);
    Vec<Vec<std::pair<int, int>>> graph(N);
    for (int i = 0; i < N - 1; ++i) {
        std::cin >> A[i] >> B[i] >> W[i];
        A[i] -= 1;
        B[i] -= 1;
        graph[A[i]].emplace_back(B[i], W[i]);
        graph[B[i]].emplace_back(A[i], W[i]);
    }    
    Vec<bool> shop(N);
    while (S--) {
        int x;
        std::cin >> x;
        x -= 1;
        shop[x] = true;
    }
    std::array<Vec<int>, 20> parent;
    parent[0] = Vec<int>(N);
    Vec<int> in(N), out(N);
    Vec<ll> nearest(N, INF), depth(N);
    int timer = 0;
    RecLambda([&](auto&& dfs, const int u, const int p, const ll d) -> void {
        parent[0][u] = p;
        in[u] = timer++;
        depth[u] = d;
        if (shop[u]) {
            nearest[u] = 0;
        }
        for (const auto [v, c]: graph[u]) {
            if (v != p) {
                dfs(v, u, d + c);
                nearest[u] = std::min(nearest[u], nearest[v] + c);
            }
        }
        out[u] = timer;
    })(E, E, 0);
    std::array<Vec<ll>, 20> min;
    min[0] = Vec<ll>(N);
    for (int i = 0; i < N; ++i) {
        min[0][i] = nearest[i] - depth[i];
    }
    for (int i = 0; i < 19; ++i) {
        parent[i + 1] = Vec<int>(N);
        min[i + 1] = Vec<ll>(N);
        for (int j = 0; j < N; ++j) {
            parent[i + 1][j] = parent[i][parent[i][j]];
            min[i + 1][j] = std::min(min[i][j], min[i][parent[i][j]]);
        }
    }
    while (Q--) {
        int e, u;
        std::cin >> e >> u;
        e -= 1;
        u -= 1;
        const auto p = (parent[0][A[e]] == B[e] ? A[e] : B[e]);
        if (in[p] <= in[u] and out[u] <= out[p]) {
            ll ans = INF;
            const auto add = depth[u];
            for (int i = 19; i >= 0; --i) {
                if (depth[parent[i][u]] >= depth[p]) {
                    ans = std::min(ans, min[i][u] + add);
                    u = parent[i][u];
                }
            }
            ans = std::min(ans, min[0][p] + add);
            if (ans == INF) {
                std::cout << "oo\n";
            }
            else {
                std::cout << ans << '\n';
            }
        }
        else {
            std::cout << "escaped\n";
        }
    }
    return 0;
}

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