Submission #1184015

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184015		crafticat	Valley (BOI19_valley)	C++20	0 / 100	195 ms	29172 KiB

valley

#include <iostream>
#include <vector>
#include <map>
using namespace std;


#define F0R(i, n) for (ll i = 0; i < n;i++)
#define FOR(i, j , n) for (ll i = j ; i< n;i++)
using ll = long long;

template<typename T>
using V = vector<T>;
using vi = V<ll>;
using pi = pair<ll,ll>;
constexpr ll INF = 1e9 + 7;

struct Seg {
    Seg *left = nullptr, *right = nullptr;
    ll l, r, mid;
    ll v = INF, lazy = 0;

    Seg(ll l, ll r) : l(l), r(r), mid((l + r) / 2) {
        if (r -l  > 1) {
            left = new Seg(l, mid), right = new Seg(mid, r);
        }
    }

    void push() {
        if (lazy == 0) return;

        if (r - l > 1) {
            left->lazy += lazy; right->lazy += lazy;
        }

        v += lazy;
        lazy = 0;
    }

    ll q(ll a, ll b) {
        push();
        if (b <= l || a >= r) return INF;
        if (a <= l && b >= r) return v;

        return min(left->q(a,b), right->q(a,b));
    }

    void pollUpdate(ll x, ll u) {
        push();
        if (r - l <= 1) {
            v = u;
            return;
        }

        if (x < mid)
            left->pollUpdate(x, u);
        else
            right->pollUpdate(x, u);

        left->push();
        right->push();
        v = min(left->v, right->v);
    }

    void update(ll a, ll b, ll u) {
        push();
        if (b <= l || a >= r) return;
        if (a <= l && b >= r) {
            lazy += u;
            push();
            return;
        }

        left->update(a,b, u); right->update(a,b,u);
        v = min(left->v, right->v);
    }
};

V<V<pi>> queries; // Node -> index of edge, index of query
vi ans;
V<V<tuple<ll, ll, ll>>> g; // y, index, w
V<ll> dp;
V<bool> spec;

void computeDp(ll x, ll p) {
    if (spec[x]) dp[x] = 0;

    for (auto [y, i, w] : g[x]) {
        if (y == p) continue;
        computeDp(y, x);
        dp[x] = min(dp[x], dp[y] + w);
    }
}

vi updates;
Seg* seg;

void dfs(ll x, ll p, map<ll, ll> &path, ll d = 0) {
    for (auto [edge, i] : queries[x]) {
        if (!path.count(edge))  {
            ans[i] = -1; continue;
        }

        ans[i] = seg->q(path[edge], 1e9);
    }

    for (auto [y, i, w] : g[x]) {
        if (y == p) continue;
        path[i] = d + 1;

        seg->update(0,1e9, w);
        seg->pollUpdate(d + 1, dp[y]);

        dfs(y, x, path, d + 1);

        seg->pollUpdate(d + 1, INF);
        seg->update(0,1e9, -w);
        path.erase(i);
    }
}

int main() {
    ll n, s, q, e; cin >> n >> s >> q >> e;
    g.resize(n + 1);
    spec.resize(n + 1);
    dp.resize(n + 1, INF);
    queries.resize(n + 1);
    ans.resize(q);

    F0R(i, n - 1) {
        ll a, b, c; cin >> a >> b >> c;
        g[a].emplace_back(b, i, c);
        g[b].emplace_back(a, i, c);
    }

    F0R(i, s) {
        ll x; cin >> x;
        spec[x] = 1;
    }

    F0R(i, q) {
        ll edge, node; cin >> edge >> node; edge--;
        queries[node].emplace_back(edge, i);
    }

    computeDp(e, -1);
    map<ll, ll> m;
    seg = new Seg(0, n + 1);

    dfs(e, -1, m);

    F0R(i, q) {
        if (ans[i] == -1) {
            cout << "escaped\n";
        }
        else if (ans[i] >= INF)
            cout << "oo\n";
        else cout << ans[i] << "\n";
    }
}

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