Submission #958276

#	Time	Username	Problem	Language	Result	Execution time	Memory
958276		Szil	Two Currencies (JOI23_currencies)	C++14	100 / 100	601 ms	137308 KiB

currencies

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define int ll

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, bool idk) : 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, false);
    } 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, false);
    } 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];
vector<ll> 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<ll> &comp, int u, int p = -1) {

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

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

vector<ll> comp = {0};
void build_tree() {
    sort(comp.begin(), comp.end());
    comp.erase(unique(comp.begin(), comp.end()), comp.end());
    g[0].emplace_back(1);
    dfs2(comp, 0);
}

signed 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++) {
        ll p, c; cin >> p >> c;
        auto [u, v] = edges[p-1];
        if (tin[u] > tin[v]) swap(u, v);
        comp.emplace_back(c);
        checkpoints[v].emplace_back(c);
    }

    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, MAXN, y)) << "\n";
    }
    return 0;
}

Compilation message (stderr)

currencies.cpp: In constructor 'Node::Node(ll, ll, bool)':
currencies.cpp:14:9: warning: 'Node::cnt' will be initialized after [-Wreorder]
   14 |     int cnt = 0;
      |         ^~~
currencies.cpp:12:11: warning:   'Node* Node::l' [-Wreorder]
   12 |     Node *l, *r;
      |           ^
currencies.cpp:16:5: warning:   when initialized here [-Wreorder]
   16 |     Node(ll x, int y, bool idk) : sum(x), cnt(y), l(nullptr), r(nullptr) {}
      |     ^~~~
currencies.cpp: In function 'int main()':
currencies.cpp:150:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  150 |         auto [u, v] = edges[p-1];
      |              ^

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