Submission #1110887

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110887		f0rizen	Valley (BOI19_valley)	C++17	100 / 100	170 ms	38576 KiB

valley

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
const int inf = 1e9 + 7;
const ll infll = 1e18;

template<typename T>
istream &operator>>(istream &is, vector<T> &a) {
    for (auto &i : a) {
        is >> i;
    }
    return is;
}

struct Edge {
    int to, w;
};

struct BinaryJumps {
    static const int lg = 17;

    vector<vector<int>> up;
    vector<vector<ll>> dp;

    BinaryJumps() {}
    BinaryJumps(int n) {
        up.resize(lg, vector<int>(n, -1));
        dp.resize(lg, vector<ll>(n, infll));
    }

    void add_leaf(int v, int p, ll w) {
        up[0][v] = p;
        dp[0][v] = w;
        for (int i = 1; i < lg; ++i) {
            if (up[i - 1][v] != -1) {
                up[i][v] = up[i - 1][up[i - 1][v]];
                dp[i][v] = min(dp[i - 1][v], dp[i - 1][up[i - 1][v]]);
            }
        }
    }

    ll la(int v, const function<bool(int)> &func) {
        ll ans = infll;
        for (int i = lg - 1; i >= 0; --i) {
            if (up[i][v] == -1) {
                continue;
            }
            if (func(up[i][v])) {
                ans = min(ans, dp[i][v]);
                v = up[i][v];
            }
        }
        return ans;
    }
};

vector<vector<Edge>> g;
BinaryJumps tr;
vector<ll> d, dp;
vector<int> tin, tout;
int timer = 0;

void dfs1(int v, int p = -1) {
    tin[v] = timer++;
    for (auto [u, w] : g[v]) {
        if (u != p) {
            d[u] = d[v] + w;
            dfs1(u, v);
            dp[v] = min(dp[v], dp[u] + w);
        }
    }
    tout[v] = timer;
}

void dfs2(int v, int p = -1) {
    if (dp[v] < infll) {
        dp[v] -= d[v];
    }
    for (auto [u, w] : g[v]) {
        if (u != p) {
            tr.add_leaf(u, v, dp[v]);
            dfs2(u, v);
        }
    }
}

bool is_anc(int p, int v) {
    return tin[p] <= tin[v] && tout[v] <= tout[p];
}

int32_t main() {
#ifdef LOCAL
    freopen("/tmp/input.txt", "r", stdin);
#else
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
#endif
    int n, s, q, e;
    cin >> n >> s >> q >> e;
    --e;
    g.resize(n);
    vector<array<int, 3>> edg(n - 1);
    for (int i = 0; i < n - 1; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        --u, --v;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
        edg[i] = {u, v, w};
    }
    dp.resize(n, infll);
    for (int i = 0; i < s; ++i) {
        int v;
        cin >> v;
        --v;
        dp[v] = 0;
    }
    d.resize(n);
    tin.resize(n);
    tout.resize(n);
    dfs1(e);
    tr = BinaryJumps(n);
    dfs2(e);
    while (q--) {
        int i, v;
        cin >> i >> v;
        --i, --v;
        auto [a, b, c] = edg[i];
        if (d[a] > d[b]) {
            swap(a, b);
        }
        if (!is_anc(b, v)) {
            cout << "escaped\n";
            continue;
        }
        ll ans = min(dp[v], tr.la(v, [&](int u) {
            return !is_anc(u, a);
        }));
        if (ans == infll) {
            cout << "oo\n";
        } else {
            cout << ans + d[v] << "\n";
        }
    }
    return 0;
}

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