Submission #1071091

#	Time	Username	Problem	Language	Result	Execution time	Memory
1071091		Double_Slash	Valley (BOI19_valley)	C++17	100 / 100	344 ms	24152 KiB

valley

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pint = pair<int, int>;

const ll INF = 1e18;

struct St {
    int off;
    vector<ll> st;

    St(int l, int r) : off(-l + r - l + 1), st((r - l + 1) << 1, INF) {}

    ll query(int l, int r) {
        ll ret = INF;
        for (l += off, r += off; l < r; l >>= 1, r >>= 1) {
            if (l & 1) ret = min(ret, st[l++]);
            if (r & 1) ret = min(ret, st[--r]);
        }
        return ret;
    }

    void update(int i, ll v) {
        for (st[i += off] = v; i >>= 1;) st[i] = min(st[i << 1], st[i << 1 | 1]);
    }
} *st[100001];
int N, S, Q, E, a[100000], b[100000], w[100000], par[100001], depth[100001], sz[100001], s[100001], e[100001], heavy[100001], head[100001];
ll shop[100001], ps[100001];
vector<pint> adj[100001];

void dfs(int i) {
    for (auto [j, d]: adj[i]) {
        if (j == par[i]) continue;
        depth[j] = depth[i] + 1;
        ps[j] = ps[i] + d;
        s[j] = e[j] = e[i];
        par[j] = i;
        dfs(j);
        shop[i] = min(shop[i], shop[j] + d);
        sz[i] += sz[j];
        e[i] = e[j] + 1;
        if (sz[j] >= sz[heavy[i]]) heavy[i] = j;
    }
    sz[i]++;
}

void hld(int i) {
    if (heavy[i]) {
        head[heavy[i]] = head[i];
        hld(heavy[i]);
        st[i] = st[heavy[i]];
    } else st[i] = new St{depth[head[i]], depth[i]};
    for (auto [j, d]: adj[i]) {
        if (j == par[i] or j == heavy[i]) continue;
        head[j] = j;
        hld(j);
    }
}

ll query(int i, int j) {
    if (not i) return INF;
    if (depth[head[i]] >= depth[j]) return min(st[i]->query(depth[head[i]], depth[i] + 1), query(par[head[i]], j));
    return st[i]->query(depth[j], depth[i] + 1);
}

int main() {
    cin >> N >> S >> Q >> E;
    for (int i = 1; i <= N - 1; ++i) {
        cin >> a[i] >> b[i] >> w[i];
        adj[a[i]].emplace_back(b[i], w[i]);
        adj[b[i]].emplace_back(a[i], w[i]);
    }
    memset(shop, 0x3f, sizeof shop);
    while (S--) {
        int i;
        cin >> i;
        shop[i] = 0;
    }
    dfs(E), hld(E);
    for (int i = 1; i <= N; ++i) {
        st[i]->update(depth[i], shop[i] - ps[i]);
    }
    while (Q--) {
        int i, r;
        cin >> i >> r;
        if (depth[a[i]] > depth[b[i]]) swap(a[i], b[i]);
        if (s[r] < s[b[i]] or e[r] > e[b[i]]) cout << "escaped\n";
        else {
            ll ans = query(r, b[i]) + ps[r];
            if (ans >= INF) cout << "oo\n";
            else cout << ans << endl;
        }
    }
}

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