Submission #1106103

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106103		cot7302	Valley (BOI19_valley)	C++17	100 / 100	114 ms	23388 KiB

valley

#include <bits/stdc++.h>
#define ALL(X) begin(X), end(X)
using namespace std;
using i64 = long long;

template <class T>
using vec = vector<T>;

template <class T>
istream& operator>>(istream& is, vec<T>& V) {
    for (auto& x : V) is >> x;
    return is;
}

using N = pair<i64, i64>;

N op(const N& l, const N& r) {
    return {min(l.first, r.first), min(l.second, r.second)};
}

constexpr i64 inf = 4e18, owoovo = 1e18;

struct seg_tree {
    int n;
    vec<N> T;
    seg_tree() = default;

    void init(int __n) {
        n = __n;
        T.assign(n * 2, N{inf, inf});
    }

    void set(int i, N V) {
        T[i += n] = V;
        for (; i /= 2; )
            T[i] = op(T[i * 2], T[i * 2 + 1]);
    }

    N query(int l, int r) {
        N ret{inf, inf};
        for (l += n, r += n; l < r; l /= 2, r /= 2) {
            if (l & 1) ret = op(ret, T[l++]);
            if (r & 1) ret = op(ret, T[--r]);
        }
        return ret;
    }

    N& operator[](int i) {
        return T[i + n];
    }
};

seg_tree seg;

constexpr int kN = 100'000;

tuple<int, int, int> es[kN];

vec<int> G[kN];

bitset<kN> eight;

int e_to_v[kN - 1], pa[kN], hd[kN], dep[kN], hv[kN], in[kN], out[kN], ced[kN], tick;

i64 len[kN], dp[kN];

int dfs(int x, int pre) {
    hv[x] = -1;
    int ret{1}, hsz{};
    for (auto ed : G[x]) {
        auto [u, v, w] = es[ed];
        auto to = x ^ u ^ v;
        if (to != pre) {
            pa[to] = x;
            dep[to] = dep[x] + 1;
            len[to] = len[x] + w;
            e_to_v[ed] = to;
            auto to_sz = dfs(to, x);
            if (to_sz > hsz) {
                hv[x] = to;
                hsz = to_sz;
            }
            ret += to_sz;
        }
    }
    return ret;
}

void hld(int x, int pre, int head) {
    hd[x] = head;
    in[x] = tick++;
    ced[head] = in[x];
    if (hv[x] != -1)
        hld(hv[x], x, head);
    i64 mn = (eight[x] ? len[x] : inf);
    for (auto ed : G[x]) {
        auto [u, v, w] = es[ed];
        auto to = x ^ u ^ v;
        if (to != pre && to != hv[x]) {
            hld(to, x, to);
            mn = min(mn, dp[to]);
        }
    }
    seg.set(in[x], {mn, mn - 2 * len[x]});
    dp[x] = mn;
    if (x == head)
        dp[x] = seg.query(in[x], ced[head] + 1).first;
    out[x] = tick;
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, S, q, E; cin >> n >> S >> q >> E;
    E -= 1;
    seg.init(n);
    for (int i = 0; i < n - 1; i++) {
        auto& [u, v, w] = es[i];
        cin >> u >> v >> w;
        u -= 1, v -= 1;
        G[u].emplace_back(i);
        G[v].emplace_back(i);
    }
    for (int i = 0; i < S; i++) {
        int u; cin >> u;
        u -= 1;
        eight[u] = true;
    }
    dfs(E, -1);
    hld(E, -1, E);
    while (q--) {
        int e, x; cin >> e >> x;
        e -= 1, x -= 1;
        int u = e_to_v[e];
        if (u == x || (in[u] < in[x] && in[x] < out[u])) {
            int y = x;
            i64 mn{inf}, tmp{inf};
            while (hd[y] != hd[u]) {
                tmp = inf;
                tmp = min(len[x] + seg.query(in[hd[y]], in[y]).second, seg.query(in[y], ced[hd[y]] + 1).first - len[y] + len[x] - len[y]);
                mn = min(mn, tmp);
                y = pa[hd[y]];
            }
            tmp = inf;
            tmp = min(len[x] + seg.query(in[u], in[y]).second, seg.query(in[y], ced[hd[y]] + 1).first - len[y] + len[x] - len[y]);
            mn = min(mn, tmp);
            if (mn < owoovo)
                cout << mn << '\n';
            else
                cout << "oo\n";
        }
        else {
            cout << "escaped\n";
        }
    }
}

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