oj.uz

Submission #757728

# Submission time Handle Problem Language Result Execution time Memory
757728 2023-06-13T16:37:40 Z happypotato Two Currencies (JOI23_currencies) C++17
40 / 100
 5000 ms 114476 KB 
#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) << endl;
    }
}
int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);
    init(); solve();
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 13 ms 4052 KB Output is correct
6 Correct 18 ms 4164 KB Output is correct
7 Correct 22 ms 3744 KB Output is correct
8 Correct 30 ms 4208 KB Output is correct
9 Correct 21 ms 4180 KB Output is correct
10 Correct 28 ms 4228 KB Output is correct
11 Correct 25 ms 4268 KB Output is correct
12 Correct 29 ms 4264 KB Output is correct
13 Correct 14 ms 4352 KB Output is correct
14 Correct 15 ms 4308 KB Output is correct
15 Correct 17 ms 4272 KB Output is correct
16 Correct 21 ms 4180 KB Output is correct
17 Correct 24 ms 4252 KB Output is correct
18 Correct 19 ms 4264 KB Output is correct
19 Correct 13 ms 4276 KB Output is correct
20 Correct 13 ms 4204 KB Output is correct
21 Correct 13 ms 4148 KB Output is correct
22 Correct 13 ms 4272 KB Output is correct
23 Correct 22 ms 4268 KB Output is correct
24 Correct 20 ms 4180 KB Output is correct
25 Correct 23 ms 4268 KB Output is correct
26 Correct 21 ms 4264 KB Output is correct
27 Correct 15 ms 4264 KB Output is correct
28 Correct 18 ms 4264 KB Output is correct
29 Correct 13 ms 4268 KB Output is correct
30 Correct 23 ms 4180 KB Output is correct
31 Correct 26 ms 4264 KB Output is correct
32 Correct 34 ms 4180 KB Output is correct
33 Correct 14 ms 4308 KB Output is correct
34 Correct 15 ms 4352 KB Output is correct
35 Correct 13 ms 4376 KB Output is correct

Subtask #2
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 21 ms 4200 KB Output is correct
3 Correct 22 ms 4264 KB Output is correct
4 Correct 22 ms 4264 KB Output is correct
5 Correct 2999 ms 98996 KB Output is correct
6 Correct 4532 ms 83576 KB Output is correct
7 Correct 3548 ms 74128 KB Output is correct
8 Correct 2594 ms 72864 KB Output is correct
9 Correct 2373 ms 77184 KB Output is correct
10 Correct 4674 ms 108012 KB Output is correct
11 Correct 4430 ms 107816 KB Output is correct
12 Correct 4705 ms 107936 KB Output is correct
13 Correct 4628 ms 107640 KB Output is correct
14 Correct 4670 ms 107724 KB Output is correct
15 Correct 2514 ms 112920 KB Output is correct
16 Correct 2202 ms 113344 KB Output is correct
17 Correct 2723 ms 112616 KB Output is correct
18 Correct 4813 ms 107480 KB Output is correct
19 Correct 4501 ms 107240 KB Output is correct
20 Execution timed out 5044 ms 107232 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 14 ms 4384 KB Output is correct
3 Correct 13 ms 4308 KB Output is correct
4 Correct 12 ms 4376 KB Output is correct
5 Correct 1157 ms 82660 KB Output is correct
6 Correct 1299 ms 70648 KB Output is correct
7 Correct 1743 ms 91308 KB Output is correct
8 Correct 2149 ms 113636 KB Output is correct
9 Correct 2082 ms 113636 KB Output is correct
10 Correct 2111 ms 113708 KB Output is correct
11 Correct 1678 ms 114308 KB Output is correct
12 Correct 1650 ms 111992 KB Output is correct
13 Correct 1596 ms 114476 KB Output is correct
14 Correct 1177 ms 113580 KB Output is correct
15 Correct 982 ms 113560 KB Output is correct
16 Correct 1281 ms 113740 KB Output is correct
17 Correct 1318 ms 113664 KB Output is correct

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 13 ms 4052 KB Output is correct
6 Correct 18 ms 4164 KB Output is correct
7 Correct 22 ms 3744 KB Output is correct
8 Correct 30 ms 4208 KB Output is correct
9 Correct 21 ms 4180 KB Output is correct
10 Correct 28 ms 4228 KB Output is correct
11 Correct 25 ms 4268 KB Output is correct
12 Correct 29 ms 4264 KB Output is correct
13 Correct 14 ms 4352 KB Output is correct
14 Correct 15 ms 4308 KB Output is correct
15 Correct 17 ms 4272 KB Output is correct
16 Correct 21 ms 4180 KB Output is correct
17 Correct 24 ms 4252 KB Output is correct
18 Correct 19 ms 4264 KB Output is correct
19 Correct 13 ms 4276 KB Output is correct
20 Correct 13 ms 4204 KB Output is correct
21 Correct 13 ms 4148 KB Output is correct
22 Correct 13 ms 4272 KB Output is correct
23 Correct 22 ms 4268 KB Output is correct
24 Correct 20 ms 4180 KB Output is correct
25 Correct 23 ms 4268 KB Output is correct
26 Correct 21 ms 4264 KB Output is correct
27 Correct 15 ms 4264 KB Output is correct
28 Correct 18 ms 4264 KB Output is correct
29 Correct 13 ms 4268 KB Output is correct
30 Correct 23 ms 4180 KB Output is correct
31 Correct 26 ms 4264 KB Output is correct
32 Correct 34 ms 4180 KB Output is correct
33 Correct 14 ms 4308 KB Output is correct
34 Correct 15 ms 4352 KB Output is correct
35 Correct 13 ms 4376 KB Output is correct
36 Correct 1 ms 2644 KB Output is correct
37 Correct 21 ms 4200 KB Output is correct
38 Correct 22 ms 4264 KB Output is correct
39 Correct 22 ms 4264 KB Output is correct
40 Correct 2999 ms 98996 KB Output is correct
41 Correct 4532 ms 83576 KB Output is correct
42 Correct 3548 ms 74128 KB Output is correct
43 Correct 2594 ms 72864 KB Output is correct
44 Correct 2373 ms 77184 KB Output is correct
45 Correct 4674 ms 108012 KB Output is correct
46 Correct 4430 ms 107816 KB Output is correct
47 Correct 4705 ms 107936 KB Output is correct
48 Correct 4628 ms 107640 KB Output is correct
49 Correct 4670 ms 107724 KB Output is correct
50 Correct 2514 ms 112920 KB Output is correct
51 Correct 2202 ms 113344 KB Output is correct
52 Correct 2723 ms 112616 KB Output is correct
53 Correct 4813 ms 107480 KB Output is correct
54 Correct 4501 ms 107240 KB Output is correct
55 Execution timed out 5044 ms 107232 KB Time limit exceeded
56 Halted 0 ms 0 KB -