제출 #1370647

#제출 시각아이디문제언어결과실행 시간메모리
1370647tranvinhhuy2010Valley (BOI19_valley)C++20
100 / 100
99 ms40268 KiB
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int nmax = 1e5 + 5, lg = 17;
const ll inf = 1e17;
int n, s, q, e, up[nmax][20], in[nmax], out[nmax], timer;
ll d[nmax], mn[nmax][20], dp[nmax];
vector <pair <int, ll>> g[nmax];
bool shop[nmax];
pair <int, int> road[nmax];

void dfs(int u) {
    dp[u] = inf;
    if (shop[u]) dp[u] = 0;
    in[u] = ++timer;

    for (auto [v, w] : g[u]) {
        if (v==up[u][0]) continue;

        d[v] = d[u] + w;
        up[v][0] = u;
        dfs(v);
        dp[u] = min(dp[u], w + dp[v]);
    }

    mn[u][0] = dp[u] - d[u];
    out[u] = timer;
}

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

    cin >> n >> s >> q >> e;
    for (int i=1; i<n; i++) {
        int u, v; ll w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
        road[i] = {u, v};
    }
    while (s--) {
        int u; cin >> u;
        shop[u] = true;
    }

    dfs(e);
    for (int j=1; j<=lg; j++) {
        for (int i=1; i<=n; i++) {
            up[i][j] = up[up[i][j - 1]][j - 1];
            mn[i][j] = min(mn[i][j - 1], mn[up[i][j - 1]][j - 1]);
        }
    }

    while (q--) {
        int i, r; cin >> i >> r;
        auto [u, v] = road[i];
        if (d[u]<d[v]) swap(u, v);

        if (in[u]<=in[r] && in[r]<=out[u]) {
            ll ans = inf;
            int cur = r;
            for (int j=lg; j>=0; j--) {
                if (d[up[cur][j]]>=d[u]) {
                    ans = min(ans, mn[cur][j]);
                    cur = up[cur][j];
                }
            }

            ans = min(ans, mn[cur][0]);
            if (ans>=1e14) cout << "oo\n";
            else cout << d[r] + ans << '\n';
        }
        else cout << "escaped\n";
    }

    return 0;
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…