Submission #932265

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

    auto calc = [&](int begin, int nope) -> void {
        std::vector<int> vis(n);
        int ans = Inf;
        std::queue<std::pair<int, int>> qq;
        qq.emplace(0, begin);
        while(!qq.empty()) {
            auto [d, node] = qq.front();
            //std::cerr << d << " " << node << "\n";
            qq.pop();
            if(vis[node]++) {
                continue;
            } else if(shops[node]) {
                ans = std::min(ans, d);
                continue;
            }

            for(auto [child, dd] : adj[node]) {
                if(node == nope && child == par[node][0]) {
                    continue;
                }

                qq.emplace(d + dd, child);
            }
        }

        if(ans == Inf) {
            std::cout << "oo\n";
        } else {
            std::cout << ans << "\n";
        }
        return;
    };

    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]) {
            calc(R, node);
        } 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: 0 / 41