Submission #916755

#	Time	Username	Problem	Language	Result	Execution time	Memory
916755		happypotato	Two Currencies (JOI23_currencies)	C++17	100 / 100	4979 ms	120236 KiB

currencies

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define ff first
#define ss second
#define pb push_back
// global
// persistent segment tree (point add range sum)
struct Node {
    int val, cnt;
    Node *l, *r;
 
    Node() : val(0), cnt(0), l(nullptr), r(nullptr) {}
    Node(int x, int y) : val(x), cnt(y), l(nullptr), r(nullptr) {}
    Node(Node *ll, Node *rr) : val(ll->val + rr->val), cnt(ll->cnt + rr->cnt), l(ll), r(rr) {}
};
const int mxN = 1e5 + 1;
int n;
Node *segstore[mxN];
Node *SegBuild(int l = 1, int r = n) {
    if (l == r) {
        return new Node();
    }
    int mid = (l + r) >> 1;
    return new Node(SegBuild(l, mid), SegBuild(mid + 1, r));
}
Node *SegUpdate(Node *seg, int pos, int val, int l = 1, int r = n) {
    if (l == r) {
        return new Node(seg->val + val, seg->cnt + 1);
    }
    int mid = (l + r) >> 1;
    if (pos <= mid) {
        return new Node(SegUpdate(seg->l, pos, val, l, mid), seg->r);
    } else {
        return new Node(seg->l, SegUpdate(seg->r, pos, val, mid + 1, r));
    }
    return new Node();
}
pii SegQuery(Node *seg, int &tl, int &tr, int l = 1, int r = n) {
    if (tl <= l && r <= tr) {
        return {seg->val, seg->cnt};
    }
    int mid = (l + r) >> 1;
    pii res = {0, 0};
    pii ret;
    if (tl <= mid) {
        ret = SegQuery(seg->l, tl, tr, l, mid);
        res.ff += ret.ff; res.ss += ret.ss;
    }
    if (tr > mid) {
        ret = SegQuery(seg->r, tl, tr, mid + 1, r);
        res.ff += ret.ff; res.ss += ret.ss;
    }
    return res;
}
// hld
vector<int> adj[mxN];
int par[mxN], rr[mxN], sz[mxN];
int heavy[mxN]; // heavy edge for children
int root[mxN]; // root of heavy edges
int corr[mxN]; // euler tour to map to segtree
void HLDInit(int u = 1, int pp = 0) {
    par[u] = pp;
    rr[u] = rr[pp] + 1;
    sz[u] = 1;
    pii big = {-1, -1};
    for (int v : adj[u]) {
        if (v != pp) {
            HLDInit(v, u);
            sz[u] += sz[v];
            if (sz[v] > big.ff) big = {sz[v], v};
        }
    }
    heavy[u] = big.ss;
}
int segptr = 1;
void HLDProcess(int u = 1, int pp = 0, int high = 1) {
    root[u] = high;
    corr[u] = segptr++;
    if (heavy[u] == -1) return;
    HLDProcess(heavy[u], u, high);
    for (int v : adj[u]) {
        if (v != heavy[u] && v != pp) HLDProcess(v, u, v);
    }
}
int HLDLCA(int u, int v) {
    while (root[u] != root[v]) {
        if (rr[root[u]] > rr[root[v]]) swap(u, v);
        v = par[root[v]];
    }
    return (rr[u] < rr[v] ? u : v);
}
void HLDUpdate(int &ver, int u, int v, int &val) {
    // depth[u] < depth[v], update v
    if (rr[u] > rr[v]) swap(u, v);
    // cerr << "HLDUPDATE " << u << ' ' << v << endl;
    segstore[ver] = SegUpdate(segstore[ver - 1], corr[v], val);
}
pii HLDQueryAnces(int &ver, int u, int v) {
    int ptr1, ptr2;
    pii res = {0, 0};
    pii ret;
    while (root[u] != root[v]) {
        ptr1 = corr[u]; ptr2 = corr[root[u]];
        if (ptr1 > ptr2) swap(ptr1, ptr2);
        ret = SegQuery(segstore[ver], ptr1, ptr2);
        res.ff += ret.ff; res.ss += ret.ss;
        u = par[root[u]];
    }
    if (rr[u] > rr[v]) swap(u, v);
    if (u != v) {
        ptr1 = corr[heavy[u]]; ptr2 = corr[v];
        if (ptr1 > ptr2) swap(ptr1, ptr2);
        ret = SegQuery(segstore[ver], ptr1, ptr2);
        res.ff += ret.ff; res.ss += ret.ss;
    }
    return res;
}
pii HLDQuery(int &ver, int u, int v) {
    int lca = HLDLCA(u, v);
    pii lhs = HLDQueryAnces(ver, u, lca);
    pii rhs = HLDQueryAnces(ver, v, lca);
    // cerr << "HLDQUERY\n";
    // cerr << ver << ' ' << u << ' ' << v << ' ' << lca << endl;
    // cerr << lhs.ff << ' ' << lhs.ss << endl;
    // cerr << rhs.ff << ' ' << rhs.ss << endl;
    return {lhs.ff + rhs.ff, lhs.ss + rhs.ss};
}
void init() {
    // init
 
}
void solve() {
    // solve
    int m, q;
    cin >> n >> m >> q;
    pii edges[n];
    for (int i = 1; i <= n - 1; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].pb(v);
        adj[v].pb(u);
        edges[i] = {u, v};
    }
 
    HLDInit();
    HLDProcess();
    pii updates[m + 1];
    for (int i = 1; i <= m; i++) {
        cin >> updates[i].ff >> updates[i].ss;
    }
    sort(updates + 1, updates + m + 1, [&](pii &lhs, pii &rhs) { return lhs.ss < rhs.ss; });
    
    segstore[0] = SegBuild();
    for (int i = 1; i <= m; i++) {
        HLDUpdate(i, edges[updates[i].ff].ff, edges[updates[i].ff].ss, updates[i].ss);
    }
 
    while (q--) {
        int s, t, x, y;
        cin >> s >> t >> x >> y;
        int lb = 0, rb = m;
        pii ret;
        while (lb < rb) {
            int mid = (lb + rb + 1) >> 1;
            ret = HLDQuery(mid, s, t);
            if (ret.ff <= y) {
                lb = mid;
            } else {
                rb = mid - 1;
            }
        }
        ret = HLDQuery(lb, s, t);
        // cerr << lb << ' ' << ret.ff << ' ' << ret.ss << endl;
        // cerr << HLDQuery(m, s, t).ff << ' ' << HLDQuery(m, s, t).ss << endl;
        x -= HLDQuery(m, s, t).ss - HLDQuery(lb, s, t).ss;
        cout << (x < 0 ? -1 : x) << '\n';
    }
}
int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);
    init(); solve();
}

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