Submission #1105786

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105786		vjudge1	Valley (BOI19_valley)	C++17	0 / 100	3080 ms	10392 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], 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] + 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] = 1e9;
    if (spec[u] == 1) {
        sub[u] = dep[u];
    }
    for (auto [v, c] : gr[u]) {
        if (v != p) {
            build(v, u);
            sub[u] = std::min(sub[u], sub[v]);
        }
    }
}

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 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);
    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] == 1e9) {
            std::cout << "oo\n";
            continue;
        }
        int mn = 1e9;
        int u = r;
        while (u != edges[i].first) {
            mn = std::min(mn, sub[u] - 2 * dep[u]);
            u = anc[0][u];
        }
        std::cout << dep[r] + mn << "\n";
    }
    return 0;
}

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