제출 #1350958

#제출 시각아이디문제언어결과실행 시간메모리
1350958msab3fValley (BOI19_valley)C++20
100 / 100
93 ms34464 KiB
#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 100'000 + 10;
const int MAX_LG = 17;
const int MAX_Q = 100'000 + 10;
const long long INF = 1e16;

int n, s, q, r, h[MAX_N], par[MAX_N][MAX_LG];
vector<pair<int, int>> adj[MAX_N], edges;
long long d[MAX_N], dp[MAX_N], mn[MAX_N][MAX_LG];

void dfs(int u, int p) {
    for (auto [v, w] : adj[u]) {
        if (v != p) {
            h[v] = h[u] + 1;
            d[v] = d[u] + w;
            par[v][0] = u;
            dfs(v, u);
            dp[u] = min(dp[u], dp[v] + w);
        }
    }
}

int get_par(int u, int k) {
    for (int i = 0; k != 0; ++i, k >>= 1) {
        if (k & 1) {
            u = par[u][i];
        }
    }
    return u;
}

long long get_mn(int u, int k) {
    long long res = INF;
    for (int i = 0; k != 0; ++i, k >>= 1) {
        if (k & 1) {
            res = min(res, mn[u][i]);
            u = par[u][i];
        }
    }
    return res;
}

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

    cin >> n >> s >> q >> r;

    for (int e = 1; e <= n - 1; ++e) {
        int u, v, w;
        cin >> u >> v >> w;
        edges.push_back({u, v});
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    fill_n(dp + 1, n, INF);

    for (int i = 1; i <= s; ++i) {
        int c;
        cin >> c;
        dp[c] = 0;
    }

    dfs(r, -1);

    for (int u = 1; u <= n; ++u) {
        mn[u][0] = dp[u] - d[u];
    }
    for (int i = 1; i < MAX_LG; ++i) {
        for (int u = 1; u <= n; ++u) {
            par[u][i] = par[par[u][i - 1]][i - 1];
            mn[u][i] = min(mn[u][i - 1], mn[par[u][i - 1]][i - 1]);
        }
    }

    while (q--) {
        int e, v;
        cin >> e >> v;

        auto [eu, ev] = edges[e - 1];
        if  (h[eu] < h[ev]) swap(eu, ev);

        if (h[eu] > h[v] || get_par(v, h[v] - h[eu]) != eu) {
            cout << "escaped\n";
        } else {
            long long res = d[v] + get_mn(v, h[v] - h[eu] + 1);
            if (res >= INF / 10) {
                cout << "oo\n";
            } else {
                cout << res << '\n';
            }
        }
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...