Submission #958262

#	Time	Username	Problem	Language	Result	Execution time	Memory
958262		Szil	Two Currencies (JOI23_currencies)	C++17	28 / 100	273 ms	92932 KiB

currencies

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int MAXN = 100'001;
const int MAXK = 20;

struct Node {
    Node *l, *r;
    ll sum = 0;
    int cnt = 0;

    Node(ll x, int y) : sum(x), cnt(y), l(nullptr), r(nullptr) {}
    Node(Node *a, Node *b) : l(a), r(b) {
        if (a) {
            sum += a->sum;
            cnt += a->cnt;
        }
        if (b) {
            sum += b->sum;
            cnt += b->cnt;
        }
    }
};

Node *build(int tl, int tr) {
    if (tl == tr) {
        return new Node(0, 0);
    } else {
        int tm = (tl + tr) / 2;
        return new Node(build(tl, tm), build(tm+1, tr));
    }
}

Node *upd(Node *v, int tl, int tr, int pos, ll val, ll cnt) {
    if (tl == tr) {
        return new Node(v->sum + val, v->cnt + cnt);
    } else {
        int tm = (tl + tr) / 2;
        if (pos <= tm) {
            return new Node(upd(v->l, tl, tm, pos, val, cnt), v->r);
        } else {
            return new Node(v->l, upd(v->r, tm+1, tr, pos, val, cnt));
        }
    }
}

ll qry(Node *u, Node *v, Node *lca, int tl, int tr, ll silver) {
    if (tl == tr) {
        ll val = u->sum + v->sum - 2 * lca->sum;
        ll golds = u->cnt + v->cnt  - 2 * lca->cnt;
        ll base = golds ? val / golds : 0;
        ll bought = base ? silver / base : 0;
        return max(0ll, golds - bought);
    } else {
        int tm = (tl + tr) / 2;
        ll val = u->l->sum + v->l->sum - 2 * lca->l->sum;
        if (val <= silver) {
            return qry(u->r, v->r, lca->r, tm+1, tr, silver - val);
        } else {
            ll golds = u->r->cnt + v->r->cnt - 2 * lca->r->cnt;
            return golds + qry(u->l, v->l, lca->l, tl, tm, silver);
        }
    }
}

vector<int> g[MAXN];
int up[MAXN][MAXK], tin[MAXN], tout[MAXN], n, m, q, timer = 1;
Node *root[MAXN];
ll cost[MAXN], checkpoints[MAXN];

void dfs(int u, int p = -1) {
    tin[u] = timer++;
    for (int v : g[u]) {
        if (v != p) {
            up[v][0] = u;
            dfs(v, u);
        }
    }
    tout[u] = timer++;
}

bool is_ancestor(int u, int v) {
    return tin[u] <= tin[v] && tout[v] <= tout[u];
}

int lca(int u, int v) {
    if (is_ancestor(u, v)) return u;
    if (is_ancestor(v, u)) return v;
    for (int k = MAXK-1; k >= 0; k--) {
        if (up[u][k] && !is_ancestor(up[u][k], v)) {
            u = up[u][k];
        }
    }
    return up[u][0];
}

void prelift() {
    dfs(1);
    for (int k = 1; k < MAXK; k++) {
        for (int i = 1; i <= n; i++) {
            up[i][k] = up[up[i][k-1]][k-1];
        }
    }
}

void dfs2(const vector<int> &comp, int u, int p = -1) {

    if (p == -1) {
        root[u] = build(1, n);
    } else if (cost[u]) {
        int pos = lower_bound(comp.begin(), comp.end(), cost[u])-comp.begin();
        root[u] = upd(root[up[u][0]], 1, n, pos, cost[u], checkpoints[u]);
    } else {
        root[u] = root[up[u][0]];
    }

    for (int v : g[u]) {
        if (v != p) dfs2(comp, v, u);
    }
}

void build_tree() {
    vector<int> comp = {0};
    for (int i = 1; i <= n; i++) {
        comp.emplace_back(cost[i]);
    }
    sort(comp.begin(), comp.end());
    comp.erase(unique(comp.begin(), comp.end()), comp.end());
    g[0].emplace_back(1);
    dfs2(comp, 0);
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m >> q;
    vector<pair<int, int>> edges;
    for (int i = 1; i <= n-1; i++) {
        int u, v; cin >> u >> v;
        edges.emplace_back(u, v);
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }

    prelift();

    for (int i = 1; i <= m; i++) {
        int p, c; cin >> p >> c;
        auto [u, v] = edges[p-1];
        if (tin[u] > tin[v]) swap(u, v);
        cost[v] += c;
        checkpoints[v]++;
    }

    build_tree();

    while (q--) {
        ll s, t, x, y; cin >> s >> t >> x >> y;
        int v = lca(s, t);
        cout << max(-1ll, x-qry(root[s], root[t], root[v], 1, n, y)) << "\n";
    }
    return 0;
}

Compilation message (stderr)

currencies.cpp: In constructor 'Node::Node(ll, int)':
currencies.cpp:12:9: warning: 'Node::cnt' will be initialized after [-Wreorder]
   12 |     int cnt = 0;
      |         ^~~
currencies.cpp:10:11: warning:   'Node* Node::l' [-Wreorder]
   10 |     Node *l, *r;
      |           ^
currencies.cpp:14:5: warning:   when initialized here [-Wreorder]
   14 |     Node(ll x, int y) : sum(x), cnt(y), l(nullptr), r(nullptr) {}
      |     ^~~~

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