Submission #1063715

#	Time	Username	Problem	Language	Result	Execution time	Memory
1063715		aufan	Two Currencies (JOI23_currencies)	C++17	100 / 100	1135 ms	56572 KiB

currencies

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

using namespace std;

struct fenwick {
        int n;
        vector<pair<int, int>> fen;
        fenwick(int n) : n(n) {
                fen = vector<pair<int, int>>(n + 5);
        }
        pair<int, int> merge(pair<int, int> a, pair<int, int> b) {
                pair<int, int> ret = {a.fi + b.fi, a.se + b.se};
                return ret;
        }
        void add(int x, int val) {
                ++x;
                for(;x <= n + 2; x += x & -x) fen[x].fi += val, fen[x].se += 1;
        }
        pair<int, int> get(int x) {
                pair<int, int> res = {0ll, 0ll};
                for (;x > 0; x -= x & -x) res = merge(res, fen[x]);
                return res;
        }
        pair<int, int> get(int l, int r) {
                ++l; ++r;
                pair<int, int> vr = get(r), vl = get(l - 1);
                return {vr.fi - vl.fi, vr.se - vl.se};
        }
};


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

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

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

        vector<pair<int, int>> cp; // checkpoint
        for (int i = 0; i < m; i++) {
                int p, c;
                cin >> p >> c;
                --p;

                cp.push_back({p, c});
        }
        sort(cp.begin(), cp.end(),
                [&](pair<int, int> x, pair<int, int> y) {
                        return x.se < y.se;
                }
        );

        int tim = -1;
        vector<int> rt(n), sz(n), dep(n, -1), par(n), tin(n);
        vector<vector<int>> ch(n);

        function<void(int, int)> dfs = [&](int x, int p) {
                par[x] = p;
                dep[x] = dep[p] + 1;
                sz[x] = 1;

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

                        dfs(z, x);
                        
                        sz[x] += sz[z];
                }

                sort(v[x].begin(), v[x].end(),
                        [&](int x, int y) {
                                return sz[x] > sz[y];
                        }
                );
        };

        dfs(0, -1);

        function<void(int, int, int)> dfs2 = [&](int x, int p, int root) {
                tin[x] = ++tim;
                rt[x] = root;
                ch[root].push_back(x);

                bool ok = 1;
                for (auto z : v[x]) {
                        if (z == p) continue;

                        if (ok) {
                                dfs2(z, x, root);
                                
                                ok = 0;
                        } else {
                                dfs2(z, x, z);
                        }
                }
        };

        dfs2(0, -1, 0);

        vector<int> s(q), t(q), x(q), y(q);
        vector<pair<int, int>> init(q), ans(q);
        vector<vector<tuple<int, int, int>>> qr(m);
        for (int i = 0; i < q; i++) {
                cin >> s[i] >> t[i] >> x[i] >> y[i];
                --s[i]; --t[i];

                int lo = 0, hi = m - 1;
                qr[(lo + hi) / 2].push_back({i, lo, hi});
        }

        for (int _ = 0; _ < 17; _++) {
                vector<vector<tuple<int, int, int>>> tmp(m);
                vector<pair<int, int>> val(n);

                fenwick fw(n);

                auto get = [&](int x, int y) {
                        pair<int, int> res = {0ll, 0ll};
                        while (rt[x] != rt[y]) {
                                if (dep[rt[x]] < dep[rt[y]]) swap(x, y);

                                res = fw.merge(res, fw.get(tin[rt[x]] + 1, tin[x]));
                                res = fw.merge(res, val[tin[rt[x]]]);
                                x = par[rt[x]];
                        }

                        if (dep[x] < dep[y]) swap(x, y);        
                        
                        res = fw.merge(res, fw.get(tin[y] + 1, tin[x]));

                        return res;
                };

                for (int i = 0; i < m; i++) {
                        auto [p, c] = cp[i];
                        int a_ = a[p], b_ = b[p];
                        if (dep[a_] < dep[b_]) swap(a_, b_);

                        fw.add(tin[a_], c);
                        val[tin[a_]].fi += c;
                        val[tin[a_]].se += 1;

                        for (auto [id, lo, hi] : qr[i]) {
                                auto res = get(s[id], t[id]);

                                if (res.fi <= y[id]) {
                                        ans[id] = res;
                                        lo = i + 1;
                                } else {
                                        hi = i - 1;
                                }

                                tmp[(lo + hi) / 2].push_back({id, lo, hi});
                        }
                }

                if (_ == 0) {
                        for (int i = 0; i < q; i++) {
                                init[i] = get(s[i], t[i]);
                        }
                }

                swap(qr, tmp);
        }

        for (int i = 0; i < q; i++) {
                ans[i].fi = max(-1ll, x[i] - (init[i].se - ans[i].se));
        }

        for (int i = 0; i < q; i++) {
                cout << ans[i].fi << '\n';
        }
        
        return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 28 / 28
• Subtask 3: 30 / 30
• Subtask 4: 32 / 32