제출 #1356890

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1356890		AksLolCoding	Valley (BOI19_valley)	C++17	100 / 100	91 ms	43212 KiB

valley

#include <iostream>
#include <vector>
#include <cmath>
#define inline inline __attribute__((always_inline))

using namespace std;

constexpr int N = 1e5 + 5;
constexpr int logN = static_cast<int>(log2(N));
constexpr long long INF = 1e18;

pair<int, int> edges[N];
vector<pair<int, int>> tree[N];
int timer;
int tin[N], tout[N];
bool special[N];
long long dist[N];
long long down[N];
long long updown[N];
pair<int, long long> up[N][logN + 1];
int tour[N * 2];

void dfs(int u, int p, long long d) {
    tin[u] = ++timer;

    dist[u] = d;
    long long mindown = special[u] ? d : INF;

    for (auto [v, w] : tree[u]) {
        if (v == p) continue;
        dfs(v, u, d + w);
        updown[v] = mindown;
        mindown = min(mindown, down[v]);
    }

    mindown = special[u] ? d : INF;
    for (auto it = tree[u].rbegin(); it != tree[u].rend(); ++it) {
        int v = it->first;
        if (v == p) continue;

        updown[v] = min(updown[v], mindown);
        mindown = min(mindown, down[v]);
    }

    down[u] = mindown;
    tout[u] = timer;
}

void build(int u, int p) {
    up[u][0] = {p, updown[u] - 2 * dist[p]};
    for (int i = 0; i < logN; i++) {
        up[u][i + 1].first = up[up[u][i].first][i].first;
        up[u][i + 1].second = min(up[u][i].second, up[up[u][i].first][i].second);
    }

    for (auto [v, w] : tree[u]) {
        if (v == p) continue;
        build(v, u);
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    // freopen("input.txt", "r", stdin);

    int n, k, q, r;
    cin >> n >> k >> q >> r;

    for (int e = 1; e < n; e++) {
        auto &[u, v] = edges[e];
        cin >> u >> v;
        int w;
        cin >> w;

        tree[u].emplace_back(v, w);
        tree[v].emplace_back(u, w);
    }

    while (k--) {
        int u;
        cin >> u;

        special[u] = true;
    }

    dfs(r, r, 0);
    build(r, r);

    for (int e = 1; e < n; e++) {
        auto [u, v] = edges[e];
        edges[e] = {max(tin[u], tin[v]), min(tout[u], tout[v])};
    }

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

        auto [l, r] = edges[e];

        if (tin[u] < l || tin[u] > r) {
            cout << "escaped\n";
            continue;
        }

        if (special[u]) {
            cout << "0\n";
            continue;
        }

        long long res = INF;
        for (int i = logN, v = u; i >= 0; i--) {
            if (tin[up[v][i].first] < l) continue;
            res = min(res, up[v][i].second);
            v = up[v][i].first;
        }
        res = min(res + dist[u], down[u] - dist[u]);

        if (res > INF / 2) {
            cout << "oo\n";
        } else {
            cout << res << '\n';
        }
    }
}

• 서브태스크 1: 9 / 9
• 서브태스크 2: 27 / 27
• 서브태스크 3: 23 / 23
• 서브태스크 4: 41 / 41