Submission #1018171

#	Time	Username	Problem	Language	Result	Execution time	Memory
1018171		aufan	Valley (BOI19_valley)	C++17	100 / 100	176 ms	49488 KiB

valley

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second

using namespace std;

const int inff = 1e18;
const int lim = 1e14;

struct node {
        int val, lz;
        int st, en;
        node *left, *right;

        void build(int start, int end, vector<int> &a) {
                st = start;
                en = end;
                lz = 0;

                if (st == en) {
                        val = a[st];
                        return;
                }

                int md = (st + en) / 2;
                left = new node();
                right = new node();

                left->build(st, md, a);
                right->build(md + 1, en, a);

                val = min(left->val, right->val);
        }

        void lazy() {
                left->val += lz;
                left->lz += lz;

                right->val += lz;
                right->lz += lz;

                lz = 0;
        }

        int query(int lf, int rg) {
                if (st > rg || en < lf) return inff;
                if (lf <= st && en <= rg) return val;
                lazy();
                return min(left->query(lf, rg), right->query(lf, rg));
        }

        void update(int lf, int rg, int x) {
                if (st > rg || en < lf) return;
                if (lf <= st && en <= rg) {
                        val += x;
                        lz += x;
                        return;
                }

                lazy();
                left->update(lf, rg, x);
                right->update(lf, rg, x);

                val = min(left->val, right->val);
        }
} sg;

int32_t main()
{
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        
        int n, s, q, e;
        cin >> n >> s >> q >> e;

        vector<int> a(n), b(n), c(n);
        vector<vector<pair<int, int>>> v(n + 1);
        for (int i = 1; i <= n - 1; i++) {
                cin >> a[i] >> b[i] >> c[i];

                v[a[i]].push_back({b[i], c[i]});
                v[b[i]].push_back({a[i], c[i]});
        }

        vector<int> ok(n + 1);
        for (int i = 1; i <= s; i++) {
                int x;
                cin >> x;

                ok[x] = 1;
        }

        vector<vector<pair<int, int>>> qr(n + 1);
        for (int i = 0; i < q; i++) {
                int j, x;
                cin >> j >> x;

                qr[x].push_back({j, i});
        }

        int tim = 0;
        vector<int> dep(n + 1), d(n + 1), tin(n + 1), tout(n + 1);

        function<void(int, int)> dfs = [&](int x, int p) {
                tin[x] = ++tim;

                for (auto [z, c] : v[x]) {
                        if (z == p) continue;

                        dep[z] = dep[x] + 1;
                        d[z] = d[x] + c;

                        dfs(z, x);
                }

                tout[x] = tim;
        };

        dfs(1, 1);

        vector<int> ans(q), val(n + 1, inff);
        for (int i = 1; i <= n; i++) {
                if (ok[i]) {
                        val[tin[i]] = d[i];
                }
        }
        sg.build(1, n, val);

        auto upper = [&](int x, int y) {
                return tin[x] <= tin[y] && tout[y] <= tout[x];
        };

        function<void(int, int)> dfs2 = [&](int x, int p) {
                for (auto [j, i] : qr[x]) {
                        if (dep[a[j]] < dep[b[j]]) swap(a[j], b[j]);

                        if (upper(a[j], x)) {
                                if (upper(a[j], e)) {
                                        ans[i] = -1;
                                } else {
                                        ans[i] = sg.query(tin[a[j]], tout[a[j]]);
                                }
                        } else {
                                if (!upper(a[j], e)) {
                                        ans[i] = -1;
                                } else {
                                        ans[i] = min(sg.query(1, tin[a[j]] - 1), sg.query(tout[a[j]] + 1, n));
                                }
                        }
                }

                for (auto [z, c] : v[x]) {
                        if (z == p) continue;

                        sg.update(1, n, c);
                        sg.update(tin[z], tout[z], -2 * c);

                        dfs2(z, x);

                        sg.update(1, n, -c);
                        sg.update(tin[z], tout[z], 2 * c);
                }
        };

        dfs2(1, 1);

        for (int i = 0; i < q; i++) {
                if (ans[i] == -1) {
                        cout << "escaped" << '\n';
                } else if (ans[i] <= lim) {
                        cout << ans[i] << '\n';
                } else {
                        cout << "oo" << '\n';
                }
        }
        
        return 0;
}

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