Submission #932294

#	Time	Username	Problem	Language	Result	Execution time	Memory
932294		MisterReaper	Valley (BOI19_valley)	C++17	100 / 100	190 ms	56204 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;
    };

    dfs(--e);
    par[e][0] = 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] = std::min(magic[node], 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";
            //std::cerr << i << " " << lg << " :: " << par[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]) {
            if(magic[node] == Inf) {
                std::cout << "oo\n";
            } else {
                int ans = std::min(magic[R], magic[node]), 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;
                    }
                }

                std::cout << ans + dist[bef] << "\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: 9 / 9
• Subtask 2: 27 / 27
• Subtask 3: 23 / 23
• Subtask 4: 41 / 41