Submission #937605

#	Time	Username	Problem	Language	Result	Execution time	Memory
937605		Sharky	Two Currencies (JOI23_currencies)	C++17	100 / 100	2416 ms	242656 KiB

currencies

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

#define int long long
const int N = 100005;
const int lg = 18;

int n, lift[N][lg], dep[N], tin[N], tout[N], sz[N], ps[N], timer = 1, we[N];
vector<pair<int, int>> adj[N];
array<int, 3> edge[N];
vector<pair<int, int>> chk;

void dfs(int u) {
    tin[u] = timer; timer++;
    sz[u] = 1;
    for (int i = 1; i < lg; i++) lift[u][i] = lift[lift[u][i - 1]][i - 1];
    for (auto& [v, w] : adj[u]) {
        if (lift[u][0] == v) continue;
        dep[v] = dep[u] + 1;
        lift[v][0] = u;
        dfs(v);
        sz[u] += sz[v];
    }
}

void pre(int u) {
    for (auto& [v, w] : adj[u]) {
        if (lift[u][0] == v) continue;
        ps[v] = ps[u] + we[v];
        pre(v);
    }
}

int jump(int sta, int dist) {
    for (int i = lg - 1; i >= 0; i--) if (dist & (1 << i)) sta = lift[sta][i];
    return sta;
}

int get_lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    u = jump(u, dep[u] - dep[v]);
    if (u == v) return u;
    for (int i = lg - 1; i >= 0; i--) {
        int ut = lift[u][i], vt = lift[v][i];
        if (ut != vt) u = ut, v = vt;
    }
    return lift[u][0];
}

int cur = 0;

struct Node {
    int sum, cnt;
    Node *l, *r;

    Node(int _sum, int _cnt) : sum(_sum), cnt(_cnt), l(nullptr), r(nullptr) {}
    Node(Node *ll, Node *rr) {
        l = ll, r = rr;
        sum = 0, cnt = 0;
        if (l) sum += l->sum, cnt += l->cnt;
        if (r) sum += r->sum, cnt += r->cnt;
    }
    Node(Node *cp) : sum(cp->sum), cnt(cp->cnt), l(cp->l), r(cp->r) {}
};

Node *roots[N << 1];

Node *build(int l = 1, int r = 2 * n) {
    if (l == r) return new Node((int) 0, (int) 0);
    int mid = (l + r) / 2;
    return new Node(build(l, mid), build(mid + 1, r));
}

Node *update(Node *node, int pos, int val, int dec, int l = 1, int r = 2 * n) {
    if (l == r) return new Node(node->sum + val, node->cnt + dec);
    int mid = (l + r) / 2;
    if (pos <= mid) return new Node(update(node->l, pos, val, dec, l, mid), node->r);
    else return new Node(node->l, update(node->r, pos, val, dec, mid + 1, r));
}

pair<int, int> query(Node *node, int ql, int qr, int l = 1, int r = 2 * n) {
    if (qr < l || r < ql) return {0, 0};
    if (ql <= l && r <= qr) return {node->sum, node->cnt};
    int mid = (l + r) / 2;
    pair<int, int> ll = query(node->l, ql, qr, l, mid);
    pair<int, int> rr = query(node->r, ql, qr, mid + 1, r);
    return {ll.first + rr.first, ll.second + rr.second};
}

int Q(Node *node, int ql, int qr, int ty) {
    pair<int, int> pr = query(node, ql, qr);
    if (ty == 0) return pr.first;
    return pr.second;
}

int silv(int curr, int u, int v, int lca, int ty) {
    // curr *= 2;
    return Q(roots[curr], 1, tin[u], ty) + Q(roots[curr], 1, tin[v], ty) - 2 * Q(roots[curr], 1, tin[lca], ty);
}

int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int m, q;
    cin >> n >> m >> q;
    for (int i = 1; i < n; i++) {
        cin >> edge[i][0] >> edge[i][1];
        adj[edge[i][0]].push_back({edge[i][1], 0});
        adj[edge[i][1]].push_back({edge[i][0], 0});
    }
    for (int i = 1; i <= m; i++) {
        int pt, c;
        cin >> pt >> c;
        chk.push_back({c, pt});
    }
    lift[1][0] = 1;
    dfs(1);
    sort(chk.begin(), chk.end());
    roots[0] = build();
    for (auto& [val, i] : chk) {
        if (dep[edge[i][0]] < dep[edge[i][1]]) swap(edge[i][0], edge[i][1]);
        ++we[edge[i][0]];
        ++cur; 
        roots[cur] = update(roots[cur - 1], tin[edge[i][0]], val, 1); 
        // cout << "update: " << tin[edge[i][0]] << ' ' << val << ' ' << 1 << '\n';
        roots[cur] = update(roots[cur], tin[edge[i][0]] + sz[edge[i][0]], -val, -1);
        // cout << "update: " << tin[edge[i][0]] + sz[edge[i][0]] << ' ' << -val << ' ' << -1 << '\n';
    }
    pre(1);
    while (q--) {
        int u, v, g, s;
        cin >> u >> v >> g >> s;
        int lca = get_lca(u, v), l = 0, r = m;
        // cout << "lca: " << lca << '\n';
        while (l < r) {
            int mid = (l + r + 1) >> 1;
            // cout <<mid << ' ' << silv(mid, u, v, lca, 0) << '\n';
            if (silv(mid, u, v, lca, 0) <= s) l = mid;
            else r = mid - 1;
        }
        int amt = silv(l, u, v, lca, 1);
        // cout << ps[u] + ps[v] - 2 * ps[lca] << ' ' << amt << '\n';
        amt = (ps[u] + ps[v] - 2 * ps[lca]) - amt;
        amt = g - amt;
        if (amt < 0) cout << "-1\n";
        else cout << amt << '\n';
    }
}

/*
10 7 9
1 8
6 3
5 9
7 9
3 1
3 4
10 1
2 6
5 6
9 4
7 4
7 4
2 4
7 4
7 4
1 4
8 6 5 3
3 9 8 0
4 7 6 15
7 4 9 3
6 4 8 0
9 10 5 16
5 3 2 4
2 8 4 3
6 1 3 3
*/

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