Submission #889383

#	Time	Username	Problem	Language	Result	Execution time	Memory
889383		Pannda	Two Currencies (JOI23_currencies)	C++17	100 / 100	710 ms	58696 KiB

currencies

#include <bits/stdc++.h>
using namespace std;

template<class T>
struct Fenwick {
    int n;
    vector<T> bit;

    Fenwick(int n) : n(n), bit(n + 1, 0) {}

    void add(int i, T delta) {
        for (i++; i <= n; i += i & -i) {
            bit[i] += delta;
        }
    }

    void add(int l, int r, T delta) {
        add(l, +delta);
        add(r, -delta);
    }

    T get(int i) {
        T res = 0;
        for (i++; i > 0; i -= i & -i) {
            res += bit[i];
        }
        return res;
    }
};

struct Tree {
    const int LOG = 17;
    int n;
    vector<vector<int>> adj;

    vector<int> begin, end;
    int tim;
    vector<int> depth;
    vector<vector<int>> lift;

    Tree(int n, vector<vector<int>> adj) : n(n), adj(adj), depth(n), lift(n, vector<int>(LOG, -1)), begin(n), end(n), tim(0) {
        function<void(int, int)> dfs = [&](int u, int p) {
            begin[u] = tim++;
            depth[u] = p == -1 ? 0 : depth[p] + 1;
            lift[u][0] = p;
            for (int i = 1; i < LOG; i++) {
                int v = lift[u][i - 1];
                if (v != -1) {
                    lift[u][i] = lift[v][i - 1];
                }
            }
            for (int v : adj[u]) {
                if (v == p) continue;
                dfs(v, u);
            }
            end[u] = tim;
        };
        dfs(0, -1);
    }

    int pos(int u) {
        return begin[u];
    }

    int pos(int u, int v) {
        if (depth[u] > depth[v]) swap(u, v);
        return begin[v];
    }

    array<int, 2> subtree(int u) {
        return array<int, 2>{ begin[u], end[u] };
    }

    array<int, 2> subtree(int u, int v) {
        if (depth[u] > depth[v]) swap(u, v);
        return array<int, 2>{ begin[v], end[v] };
    }

    int lca(int u, int v) {
        if (depth[u] > depth[v]) swap(u, v);
        for (int i = LOG - 1; i >= 0; i--) {
            int w = lift[v][i];
            if (w != -1 && depth[w] >= depth[u]) {
                v = w;
            }
        }
        if (u == v) return u;
        for (int i = LOG - 1; i >= 0; i--) {
            if (lift[u][i] != lift[v][i]) {
                u = lift[u][i];
                v = lift[v][i];
            }
        }
        return lift[u][0];
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
//    freopen("inp.inp", "r", stdin);
//    freopen("out.out", "w", stdout);

    int n, m, q;
    cin >> n >> m >> q;

    vector<vector<int>> adj(n);
    vector<array<int, 2>> edges(n - 1);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        u--;
        v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
        edges[i] = { u, v };
    }
    Tree tree(n, adj);

    vector<array<int, 2>> checkpoints(m);
    for (int i = 0; i < m; i++) {
        int p, c;
        cin >> p >> c;
        p--;
        checkpoints[i] = { p, c };
    }
    sort(checkpoints.begin(), checkpoints.end(), [&](array<int, 2> e0, array<int, 2> e1) { return e0[1] < e1[1]; });

    struct Query {
        int l, r; // number of silver piles to consider and still good, try to maximize this
        int u, v, uv;
        int x;
        long long y;
    };
    vector<Query> qs(q);
    vector<vector<int>> inbox(m + 1);

    for (int i = 0; i < q; i++) {
        int u, v, x;
        long long y;
        cin >> u >> v >> x >> y;
        u--;
        v--;
        qs[i] = { 0, m, u, v, tree.lca(u, v), x, y };
        inbox[(qs[i].l + qs[i].r + 1) >> 1].push_back(i);
    }

    const int LOG = 20;
    for (int ite = 0; ite < LOG; ite++) {
        Fenwick<long long> fen(n);
        vector<vector<int>> new_inbox(m + 1);
        for (int t = 0; t <= m; t++) {
            for (int i : inbox[t]) {
                auto &[l, r, u, v, uv, x, y] = qs[i];
                long long sum = fen.get(tree.pos(u)) + fen.get(tree.pos(v)) - 2 * fen.get(tree.pos(uv));
                if (sum <= y) {
                    l = t;
                } else {
                    r = t - 1;
                }
                new_inbox[(l + r + 1) >> 1].push_back(i);
            }
            if (t != m) {
                auto [p, c] = checkpoints[t];
                auto [ql, qr] = tree.subtree(edges[p][0], edges[p][1]);
                fen.add(ql, qr, +c);
            }
        }
        inbox = new_inbox;
    }

    Fenwick<int> fen0(n);
    for (int t = 0; t < m; t++) {
        auto [p, c] = checkpoints[t];
        auto [ql, qr] = tree.subtree(edges[p][0], edges[p][1]);
        fen0.add(ql, qr, +1);
    }

    Fenwick<int> fen(n);
    vector<int> ans(q);
    for (int t = 0; t <= m; t++) {
        for (int i : inbox[t]) {
            auto [l, r, u, v, uv, x, y] = qs[i];
            int cnt0 = fen0.get(tree.pos(u)) + fen0.get(tree.pos(v)) - 2 * fen0.get(tree.pos(uv));
            int cnt = fen.get(tree.pos(u)) + fen.get(tree.pos(v)) - 2 * fen.get(tree.pos(uv));
            int req = cnt0 - cnt;
            ans[i] = max(-1, x - req);
        }
        if (t != m) {
            auto [p, c] = checkpoints[t];
            auto [ql, qr] = tree.subtree(edges[p][0], edges[p][1]);
            fen.add(ql, qr, +1);
        }
    }

    for (int x : ans) {
        cout << x << '\n';
    }
}

Compilation message (stderr)

currencies.cpp: In constructor 'Tree::Tree(int, std::vector<std::vector<int> >)':
currencies.cpp:39:25: warning: 'Tree::lift' will be initialized after [-Wreorder]
   39 |     vector<vector<int>> lift;
      |                         ^~~~
currencies.cpp:36:17: warning:   'std::vector<int> Tree::begin' [-Wreorder]
   36 |     vector<int> begin, end;
      |                 ^~~~~
currencies.cpp:41:5: warning:   when initialized here [-Wreorder]
   41 |     Tree(int n, vector<vector<int>> adj) : n(n), adj(adj), depth(n), lift(n, vector<int>(LOG, -1)), begin(n), end(n), tim(0) {
      |     ^~~~

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