제출 #1105789

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1105789		vjudge1	Valley (BOI19_valley)	C++17	100 / 100	92 ms	39912 KiB

valley

#include <bits/stdc++.h>

const int N = 1e5 + 5;
const int L = 18;

int n, s, q, e;
std::vector<std::pair<int, int>> gr[N];
int dep[N], anc[L][N], spec[N];
int64_t dist[N], f[L][N], sub[N];
int tin[N], tout[N], tt = 0;

void dfs(int u, int p = 0) {
    tin[u] = ++tt;
    anc[0][u] = p;
    for (auto [v, c] : gr[u]) {
        if (v != p) {
            dep[v] = dep[u] + 1;
            dist[v] = dist[u] + c;
            dfs(v, u);
        }
    }
    tout[u] = tt;
}

bool is_ancestor(int a, int b) {
    return tin[a] <= tin[b] && tout[b] <= tout[a];
}

void build(int u, int p = 0) {
    sub[u] = 1e18;
    if (spec[u] == 1) {
        sub[u] = dist[u];
    }
    for (auto [v, c] : gr[u]) {
        if (v != p) {
            build(v, u);
            sub[u] = std::min(sub[u], sub[v]);
        }
    }
}

int64_t get_min(int a, int b) {
    int64_t mn = 1e18;
    for (int h = L - 1; h >= 0; h--) {
        if (dep[a] - (1 << h) >= dep[b]) {
            mn = std::min(mn, f[h][a]);
            a = anc[h][a];
        }
    }
    return mn;
}

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

    std::cin >> n >> s >> q >> e;
    std::vector<std::pair<int, int>> edges(n);
    for (int i = 1; i < n; i++) {
        int a, b, w;
        std::cin >> a >> b >> w;
        gr[a].push_back({b, w});
        gr[b].push_back({a, w});
        edges[i] = {a, b};
    }
    dfs(e);
    for (int h = 1; h < L; h++) {
        for (int i = 1; i <= n; i++) {
            anc[h][i] = anc[h - 1][anc[h - 1][i]];
        }
    }
    for (int i = 1; i < n; i++) {
        if (dep[edges[i].first] > dep[edges[i].second]) {
            std::swap(edges[i].first, edges[i].second);
        }
    }
    for (int i = 1; i <= s; i++) {
        int x;
        std::cin >> x;
        spec[x] = 1;
    }
    build(e);
    for (int i = 1; i <= n; i++) {
        f[0][i] = sub[i] - 2 * dist[i];
    }
    for (int h = 1; h < L; h++) {
        for (int i = 1; i <= n; i++) {
            f[h][i] = std::min(f[h - 1][i], f[h - 1][anc[h - 1][i]]);
        }
    }
    while (q--) {
        int i, r;
        std::cin >> i >> r;
        int x = edges[i].second;
        if (!is_ancestor(x, r)) {
            std::cout << "escaped\n";
            continue;
        }
        if (sub[x] == 1e18) {
            std::cout << "oo\n";
            continue;
        }
        std::cout << dist[r] + get_min(r, edges[i].first) << "\n";
    }
    return 0;
}

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