Submission #1037262

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037262		0npata	Two Currencies (JOI23_currencies)	C++17	100 / 100	2913 ms	540796 KiB

currencies

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

const int MXN = 1e5 + 5;
const int MXM = 1e5 + 5;

#define int long long

struct Node {
    using ptr = shared_ptr<Node>;

    ptr left, right;
    int sum = 0;
    int cnt = 0;

    Node() = default;

    Node(int sum, int cnt, ptr left = nullptr, ptr right = nullptr)
        : sum(sum), cnt(cnt), left(left), right(right) {}

    ptr get_left() {
        if (!left) left = make_shared<Node>();
        return left;
    }

    ptr get_right() {
        if (!right) right = make_shared<Node>();
        return right;
    }

    ptr update(int l, int r, int add, int tl = 0, int tr = MXN) {
        if (tl >= r || tr <= l) return make_shared<Node>(sum, cnt, left, right);
        if (tl >= l && tr <= r) return make_shared<Node>(sum + add, cnt + 1, left, right);

        int tm = (tl + tr) / 2;
        return make_shared<Node>(
            sum, cnt,
            get_left()->update(l, r, add, tl, tm),
            get_right()->update(l, r, add, tm, tr)
        );
    }

    pair<int, int> query(int i, int tl = 0, int tr = MXN) const {
        if (tl + 1 == tr) return {sum, cnt};

        int tm = (tl + tr) / 2;
        if (i < tm) {
            if (!left) return {sum, cnt};
            auto res = left->query(i, tl, tm);
            return {res.first + sum, res.second + cnt};
        } else {
            if (!right) return {sum, cnt};
            auto res = right->query(i, tm, tr);
            return {res.first + sum, res.second + cnt};
        }
    }
};

Node::ptr pers_st[MXM];

int in[MXN], out[MXN], depth[MXN], jmp[MXN][20];
vector<int> tree[MXN];
int t = 0;

void dfs1(int u, int p = -1) {
    jmp[u][0] = p;
    for (int i = 1; i < 20; i++) {
        if (jmp[u][i - 1] == -1) {
            jmp[u][i] = -1;
            continue;
        }
        jmp[u][i] = jmp[jmp[u][i - 1]][i - 1];
    }

    in[u] = t++;
    for (int v : tree[u]) {
        if (v == p) continue;
        depth[v] = depth[u] + 1;
        dfs1(v, u);
    }
    out[u] = t;
}

int lca(int u, int v) {
    if (depth[u] < depth[v]) swap(u, v);
    for (int i = 0; i < 20; i++) {
        if ((depth[u] - depth[v]) & (1 << i)) {
            u = jmp[u][i];
        }
    }
    if (u == v) return u;
    for (int i = 19; i >= 0; i--) {
        if (jmp[u][i] != jmp[v][i]) {
            u = jmp[u][i];
            v = jmp[v][i];
        }
    }
    return jmp[u][0];
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int N, M, Q;
    cin >> N >> M >> Q;

    vector<pair<int, int>> edges(N - 1);

    for (int i = 0; i < N - 1; i++) {
        int u, v;
        cin >> u >> v;
        u--; v--;
        tree[u].push_back(v);
        tree[v].push_back(u);
        edges[i] = {u, v};
    }

    dfs1(0);

    vector<pair<int, int>> cs(M);

    for (int i = 0; i < M; i++) {
        int ei, c;
        cin >> ei >> c;
        ei--;
        cs[i] = {c, ei};
    }
    sort(cs.begin(), cs.end());
    pers_st[0] = make_shared<Node>();

    for (int i = 1; i <= M; i++) {
        auto [c, ei] = cs[i - 1];
        auto [u, v] = edges[ei];
        if (depth[u] < depth[v]) swap(u, v);

        pers_st[i] = pers_st[i - 1]->update(in[u], out[u], c);
    }

    for (int i = 0; i < Q; i++) {
        int u, v, g, s;
        cin >> u >> v >> g >> s;
        u--; v--;

        int w = lca(u, v);

        auto eval = [&](int k) {
            auto [a1, a2] = pers_st[k]->query(in[u]);
            auto [b1, b2] = pers_st[k]->query(in[v]);
            auto [c1, c2] = pers_st[k]->query(in[w]);
            return pair<int, int>{a1 + b1 - 2 * c1, a2 + b2 - 2 * c2};
        };

        int l = 0;
        int r = M + 1;
        while (l + 1 < r) {
            int m = (l + r) / 2;
            auto res = eval(m);
            if (res.first > s) {
                r = m;
            } else {
                l = m;
            }
        }
        int cnt = eval(l).second;
        int tot_cnt = eval(M).second;
        if (tot_cnt - cnt > g) {
            cout << -1 << '\n';
        } else {
            cout << g - (tot_cnt - cnt) << '\n';
        }
    }

    return 0;
}

Compilation message (stderr)

currencies.cpp: In constructor 'Node::Node(long long int, long long int, Node::ptr, Node::ptr)':
currencies.cpp:14:9: warning: 'Node::cnt' will be initialized after [-Wreorder]
   14 |     int cnt = 0;
      |         ^~~
currencies.cpp:12:9: warning:   'Node::ptr Node::left' [-Wreorder]
   12 |     ptr left, right;
      |         ^~~~
currencies.cpp:18:5: warning:   when initialized here [-Wreorder]
   18 |     Node(int sum, int cnt, ptr left = nullptr, ptr right = nullptr)
      |     ^~~~

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