Submission #1265802

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265802		canhnam357	Valley (BOI19_valley)	C++20	100 / 100	163 ms	50820 KiB

valley

#include <bits/stdc++.h>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, s, q, e;
    cin >> n >> s >> q >> e;
    vector<tuple<int, int, int>> edge(n - 1);
    vector<vector<pair<int, int>>> adjw(n + 1);
    vector<vector<int>> adj(n + 1);
    for (auto &[u, v, w] : edge) {
        cin >> u >> v >> w;
        adjw[u].emplace_back(v, w);
        adjw[v].emplace_back(u, w);
        adj[v].push_back(u);
        adj[u].push_back(v);
    }
    vector<int> h(n + 1);
    vector<long long> d(n + 1);
    function<void(int, int)> dfs1 = [&](int u, int p) {
        for (auto [v, w] : adjw[u]) {
            if (v == p) continue;
            h[v] = h[u] + 1;
            d[v] = d[u] + w;
            dfs1(v, u);
        }
    };
    dfs1(e, e);
    vector<int> shop(n + 1);
    const long long inf = 1e18;
    vector<long long> g(n + 1, inf);
    for (int i = 0; i < s; i++) {
        int u;
        cin >> u;
        shop[u] = 1;
        g[u] = 0;
    }
    int timer = 0;
    vector<int> in(n + 1), out(n + 1);
    const int lg = 17; 
    vector<vector<int>> par(n + 1, vector<int>(lg));
    vector<vector<long long>> f(n + 1, vector<long long>(lg));
    function<void(int, int)> dfs2 = [&](int u, int p) {
        in[u] = timer++;
        for (auto [v, w] : adjw[u]) {
            if (v == p) continue;
            par[v][0] = u;
            dfs2(v, u);
            g[u] = min(g[u], g[v] + w);
        }
        f[u][0] = g[u];
        if (f[u][0] != inf) f[u][0] -= d[u];
        out[u] = timer++;
    };
    dfs2(e, e);
    for (int i = 1; i < lg; i++) {
        for (int j = 1; j <= n; j++) {
            if (par[j][i - 1]) {
                par[j][i] = par[par[j][i - 1]][i - 1];
                f[j][i] = min(f[j][i - 1], f[par[j][i - 1]][i - 1]);
            }
        }
    }
    for (auto &[u, v, w] : edge) {
        if (h[u] < h[v]) swap(u, v);
    }
    while (q--) {
        int ie, z;
        cin >> ie >> z;
        ie--;
        long long x = d[z];
        auto [u, v, w] = edge[ie];
        if (in[u] > in[z] || out[u] < out[z]) {
            cout << "escaped\n";
            continue;
        }
        long long mn = inf;
        int k = h[z] - h[u] + 1;
        for (int i = 0; i < lg; i++) {
            if ((k >> i) & 1) {
                mn = min(mn, f[z][i]);
                z = par[z][i];
            }
        }
        if (mn == inf) cout << "oo\n";
        else cout << x + mn << '\n';
    }
    return 0;
}

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