oj.uz

Submission #937605

# Submission time Handle Problem Language Result Execution time Memory
937605 2024-03-04T09:33:48 Z Sharky Two Currencies (JOI23_currencies) C++17
100 / 100
 2416 ms 242656 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 3 ms 12636 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 2 ms 12764 KB Output is correct
5 Correct 11 ms 15452 KB Output is correct
6 Correct 11 ms 15452 KB Output is correct
7 Correct 10 ms 14824 KB Output is correct
8 Correct 12 ms 15708 KB Output is correct
9 Correct 11 ms 15708 KB Output is correct
10 Correct 13 ms 15800 KB Output is correct
11 Correct 11 ms 15708 KB Output is correct
12 Correct 12 ms 15708 KB Output is correct
13 Correct 12 ms 15964 KB Output is correct
14 Correct 15 ms 15708 KB Output is correct
15 Correct 12 ms 15708 KB Output is correct
16 Correct 11 ms 15844 KB Output is correct
17 Correct 11 ms 15964 KB Output is correct
18 Correct 11 ms 15704 KB Output is correct
19 Correct 11 ms 15956 KB Output is correct
20 Correct 11 ms 15708 KB Output is correct
21 Correct 11 ms 15796 KB Output is correct
22 Correct 11 ms 15708 KB Output is correct
23 Correct 11 ms 15708 KB Output is correct
24 Correct 11 ms 15960 KB Output is correct
25 Correct 11 ms 15704 KB Output is correct
26 Correct 10 ms 15708 KB Output is correct
27 Correct 10 ms 15708 KB Output is correct
28 Correct 10 ms 15704 KB Output is correct
29 Correct 10 ms 15708 KB Output is correct
30 Correct 11 ms 15708 KB Output is correct
31 Correct 15 ms 15708 KB Output is correct
32 Correct 12 ms 15708 KB Output is correct
33 Correct 11 ms 15964 KB Output is correct
34 Correct 11 ms 15960 KB Output is correct
35 Correct 11 ms 15960 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12888 KB Output is correct
2 Correct 11 ms 15708 KB Output is correct
3 Correct 13 ms 15704 KB Output is correct
4 Correct 11 ms 15708 KB Output is correct
5 Correct 1157 ms 212776 KB Output is correct
6 Correct 1545 ms 182788 KB Output is correct
7 Correct 1534 ms 162316 KB Output is correct
8 Correct 1041 ms 160060 KB Output is correct
9 Correct 1133 ms 168564 KB Output is correct
10 Correct 2033 ms 231832 KB Output is correct
11 Correct 1943 ms 231956 KB Output is correct
12 Correct 1946 ms 231996 KB Output is correct
13 Correct 1935 ms 231980 KB Output is correct
14 Correct 1951 ms 231748 KB Output is correct
15 Correct 1936 ms 237212 KB Output is correct
16 Correct 1989 ms 242220 KB Output is correct
17 Correct 2016 ms 241240 KB Output is correct
18 Correct 2262 ms 232860 KB Output is correct
19 Correct 2141 ms 232640 KB Output is correct
20 Correct 2197 ms 232552 KB Output is correct
21 Correct 1135 ms 230872 KB Output is correct
22 Correct 1129 ms 230904 KB Output is correct
23 Correct 1195 ms 231244 KB Output is correct
24 Correct 1172 ms 231040 KB Output is correct
25 Correct 1289 ms 228956 KB Output is correct
26 Correct 1270 ms 231524 KB Output is correct
27 Correct 1405 ms 233896 KB Output is correct
28 Correct 844 ms 231772 KB Output is correct
29 Correct 861 ms 231876 KB Output is correct
30 Correct 1028 ms 232240 KB Output is correct
31 Correct 1068 ms 232104 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12636 KB Output is correct
2 Correct 12 ms 15820 KB Output is correct
3 Correct 13 ms 16220 KB Output is correct
4 Correct 11 ms 15804 KB Output is correct
5 Correct 1125 ms 175520 KB Output is correct
6 Correct 1082 ms 150364 KB Output is correct
7 Correct 1588 ms 198960 KB Output is correct
8 Correct 2128 ms 241744 KB Output is correct
9 Correct 2086 ms 241596 KB Output is correct
10 Correct 2116 ms 242168 KB Output is correct
11 Correct 1724 ms 242656 KB Output is correct
12 Correct 1667 ms 240124 KB Output is correct
13 Correct 1702 ms 242460 KB Output is correct
14 Correct 1104 ms 241460 KB Output is correct
15 Correct 1057 ms 241572 KB Output is correct
16 Correct 1286 ms 241596 KB Output is correct
17 Correct 1290 ms 241700 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 3 ms 12636 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 2 ms 12764 KB Output is correct
5 Correct 11 ms 15452 KB Output is correct
6 Correct 11 ms 15452 KB Output is correct
7 Correct 10 ms 14824 KB Output is correct
8 Correct 12 ms 15708 KB Output is correct
9 Correct 11 ms 15708 KB Output is correct
10 Correct 13 ms 15800 KB Output is correct
11 Correct 11 ms 15708 KB Output is correct
12 Correct 12 ms 15708 KB Output is correct
13 Correct 12 ms 15964 KB Output is correct
14 Correct 15 ms 15708 KB Output is correct
15 Correct 12 ms 15708 KB Output is correct
16 Correct 11 ms 15844 KB Output is correct
17 Correct 11 ms 15964 KB Output is correct
18 Correct 11 ms 15704 KB Output is correct
19 Correct 11 ms 15956 KB Output is correct
20 Correct 11 ms 15708 KB Output is correct
21 Correct 11 ms 15796 KB Output is correct
22 Correct 11 ms 15708 KB Output is correct
23 Correct 11 ms 15708 KB Output is correct
24 Correct 11 ms 15960 KB Output is correct
25 Correct 11 ms 15704 KB Output is correct
26 Correct 10 ms 15708 KB Output is correct
27 Correct 10 ms 15708 KB Output is correct
28 Correct 10 ms 15704 KB Output is correct
29 Correct 10 ms 15708 KB Output is correct
30 Correct 11 ms 15708 KB Output is correct
31 Correct 15 ms 15708 KB Output is correct
32 Correct 12 ms 15708 KB Output is correct
33 Correct 11 ms 15964 KB Output is correct
34 Correct 11 ms 15960 KB Output is correct
35 Correct 11 ms 15960 KB Output is correct
36 Correct 2 ms 12888 KB Output is correct
37 Correct 11 ms 15708 KB Output is correct
38 Correct 13 ms 15704 KB Output is correct
39 Correct 11 ms 15708 KB Output is correct
40 Correct 1157 ms 212776 KB Output is correct
41 Correct 1545 ms 182788 KB Output is correct
42 Correct 1534 ms 162316 KB Output is correct
43 Correct 1041 ms 160060 KB Output is correct
44 Correct 1133 ms 168564 KB Output is correct
45 Correct 2033 ms 231832 KB Output is correct
46 Correct 1943 ms 231956 KB Output is correct
47 Correct 1946 ms 231996 KB Output is correct
48 Correct 1935 ms 231980 KB Output is correct
49 Correct 1951 ms 231748 KB Output is correct
50 Correct 1936 ms 237212 KB Output is correct
51 Correct 1989 ms 242220 KB Output is correct
52 Correct 2016 ms 241240 KB Output is correct
53 Correct 2262 ms 232860 KB Output is correct
54 Correct 2141 ms 232640 KB Output is correct
55 Correct 2197 ms 232552 KB Output is correct
56 Correct 1135 ms 230872 KB Output is correct
57 Correct 1129 ms 230904 KB Output is correct
58 Correct 1195 ms 231244 KB Output is correct
59 Correct 1172 ms 231040 KB Output is correct
60 Correct 1289 ms 228956 KB Output is correct
61 Correct 1270 ms 231524 KB Output is correct
62 Correct 1405 ms 233896 KB Output is correct
63 Correct 844 ms 231772 KB Output is correct
64 Correct 861 ms 231876 KB Output is correct
65 Correct 1028 ms 232240 KB Output is correct
66 Correct 1068 ms 232104 KB Output is correct
67 Correct 3 ms 12636 KB Output is correct
68 Correct 12 ms 15820 KB Output is correct
69 Correct 13 ms 16220 KB Output is correct
70 Correct 11 ms 15804 KB Output is correct
71 Correct 1125 ms 175520 KB Output is correct
72 Correct 1082 ms 150364 KB Output is correct
73 Correct 1588 ms 198960 KB Output is correct
74 Correct 2128 ms 241744 KB Output is correct
75 Correct 2086 ms 241596 KB Output is correct
76 Correct 2116 ms 242168 KB Output is correct
77 Correct 1724 ms 242656 KB Output is correct
78 Correct 1667 ms 240124 KB Output is correct
79 Correct 1702 ms 242460 KB Output is correct
80 Correct 1104 ms 241460 KB Output is correct
81 Correct 1057 ms 241572 KB Output is correct
82 Correct 1286 ms 241596 KB Output is correct
83 Correct 1290 ms 241700 KB Output is correct
84 Correct 1292 ms 210524 KB Output is correct
85 Correct 1372 ms 178992 KB Output is correct
86 Correct 1213 ms 134572 KB Output is correct
87 Correct 2155 ms 231800 KB Output is correct
88 Correct 2128 ms 232024 KB Output is correct
89 Correct 2092 ms 231988 KB Output is correct
90 Correct 2179 ms 231948 KB Output is correct
91 Correct 2122 ms 232412 KB Output is correct
92 Correct 2237 ms 239420 KB Output is correct
93 Correct 2230 ms 240696 KB Output is correct
94 Correct 2369 ms 232476 KB Output is correct
95 Correct 2416 ms 232660 KB Output is correct
96 Correct 2346 ms 232860 KB Output is correct
97 Correct 2384 ms 232504 KB Output is correct
98 Correct 1999 ms 231236 KB Output is correct
99 Correct 1976 ms 230780 KB Output is correct
100 Correct 1986 ms 230868 KB Output is correct
101 Correct 1991 ms 231024 KB Output is correct
102 Correct 1717 ms 233900 KB Output is correct
103 Correct 1717 ms 233740 KB Output is correct
104 Correct 1663 ms 233784 KB Output is correct
105 Correct 960 ms 232392 KB Output is correct
106 Correct 869 ms 232004 KB Output is correct
107 Correct 1220 ms 231736 KB Output is correct
108 Correct 1187 ms 231716 KB Output is correct