제출 #932250

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
932250		MisterReaper	Valley (BOI19_valley)	C++17	0 / 100	120 ms	46928 KiB

valley

#include <bits/stdc++.h>
using i64 = long long;
#define int i64

constexpr int Inf = 1E14 + 5;
constexpr int N = 1E5 + 5;
constexpr int L = 20;

int par[N][L];
int dis[N][L];

void solve() {
    int n, s, q, e;
    std::cin >> n >> s >> q >> e;

    std::vector<std::array<int, 3>> edges(n - 1);
    std::vector<std::pair<int, int>> adj[n + 1];
    for(int i = 0; i < n - 1; i++) {
        std::cin >> edges[i][0] >> edges[i][1] >> edges[i][2];
        adj[--edges[i][0]].emplace_back(--edges[i][1], edges[i][2]);
        adj[edges[i][1]].emplace_back(edges[i][0], edges[i][2]);
    }

    std::vector<int> shops(n);
    for(int i = 0; i < s; i++) {
        int x;
        std::cin >> x;
        x--;
        shops[x] = true;
    }

    int timer = 0;
    std::vector<int> tin(n), tout(n), dist(n), depth(n);
    std::function<void(int)> dfs = [&](int node) -> void {
        tin[node] = ++timer;

        for(auto [child, d] : adj[node]) {
            if(tin[child] == 0) {
                par[child][0] = node;
                depth[child] = depth[node] + 1;
                dist[child] = dist[node] + d;
                dfs(child);
            }
        }

        tout[node] = ++timer;

        return;
    };

    par[e][0] = e;
    dfs(--e);

    for(int i = 0; i < n - 1; i++) {
        auto &[u, v, d] = edges[i];
        if(depth[u] > depth[v]) {
            std::swap(u, v);
        }
    }

    std::vector<int> magic(n, -1);
    dfs = [&](int node) -> void {
        magic[node] = Inf;

        for(auto [child, d] : adj[node]) {
            if(magic[child] == -1) {
                dfs(child);
                magic[node] = std::min(magic[node], magic[child]);
            }
        }

        if(shops[node]) {
            magic[node] = std::min(magic[node], dist[node]);
        } else {
            magic[node] = std::min(magic[node], Inf);
        }

        return;
    };

    dfs(e);
    for(int node = 0; node < n; node++) {
        if(magic[node] != Inf) {
            magic[node] -= 2 * dist[node];
        }
        //std::cerr << magic[node] << " \n"[node == n - 1];

        dis[node][0] = magic[par[node][0]];
    }

    for(int lg = 1; lg < L; lg++) {
        for(int i = 0; i < n; i++) {
            par[i][lg] = par[par[i][lg - 1]][lg - 1];
            dis[i][lg] = std::min(dis[i][lg - 1], dis[par[i][lg - 1]][lg - 1]);
            //std::cerr << i << " " << lg << " || " << dis[i][lg - 1] << " " << dis[par[i][lg - 1]][lg - 1] << "\n";
        }
    }

    for(int cCc = 1; cCc <= q; cCc++) {
        int I, R;
        std::cin >> I >> R;
        I--; R--;

        int node = edges[I][1];
        //std::cerr << "query: " << cCc << " ? " << I << " " << R << " :: " << node << " -> " << tin[node] << " " << tin[R] << " " << tout[R] << " " << tout[node] << "\n";
        if(tin[node] <= tin[R] && tout[R] <= tout[node]) {
            int ans = Inf, bef = R;
            for(int lg = L - 1; lg >= 0; lg--) {
                int nxt = par[R][lg];
                if(tin[node] <= tin[nxt] && tout[nxt] <= tout[node]) {
                    //std::cerr << "zipla: " << R << " " << lg << " -> " << nxt << " :: " << dis[R][lg] << "\n";
                    ans = std::min(ans, dis[R][lg]);
                    R = nxt;
                }
            }

            if(ans != Inf) {
                std::cout << ans + dist[bef] << "\n";
            } else {
                std::cout << "oo\n";
            }
        } else {
            std::cout << "escaped\n";
        }
    }
    
    return;
}

signed main() {
    #ifdef LOCAL
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
    #endif

    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL); std::cout.tie(NULL);

    int t = 1; //std::cin >> t;
    for(int i = 1; i <= t; i++) {
        solve();
    }

    return 0;
}

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