oj.uz

답안 #839358

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
839358 2023-08-29T19:50:27 Z t6twotwo Two Currencies (JOI23_currencies) C++17
100 / 100
 2957 ms 97844 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct node {
    node *l, *r;
    ll s;
    node() : s(0) {
        l = r = nullptr;
    }
    node(ll v) : s(v) {
        l = r = nullptr;
    }
    node(node *u, node *v) : l(u), r(v) {
        s = l->s + r->s;
    }
};
node *bld(int l, int r) {
    if (l + 1 == r) {
        return new node();
    }
    int m = (l + r) / 2;
    return new node(bld(l, m), bld(m, r));
}
node *add(node *p, int l, int r, int i, int v) {
    if (l + 1 == r) {
        return new node(p->s + v);
    }
    int m = (l + r) / 2;
    if (i < m) {
        return new node(add(p->l, l, m, i, v), p->r);
    } else {
        return new node(p->l, add(p->r, m, r, i, v));
    }
}
ll qry(node *p, int l, int r, int L, int R) {
    if (R <= l || r <= L) {
        return 0;
    }
    if (L <= l && r <= R) {
        return p->s;
    }
    int m = (l + r) / 2;
    return qry(p->l, l, m, L, R) + qry(p->r, m, r, L, R);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, M, Q;
    cin >> N >> M >> Q;
    vector<pair<int, int>> edges(N - 1);
    vector<vector<int>> adj(N);
    for (int i = 0; i < N - 1; i++) {
        int x, y;
        cin >> x >> y;
        x--, y--;
        edges[i] = {x, y};
        adj[x].push_back(i);
        adj[y].push_back(i);
    }
    vector<pair<int, int>> ch(M);
    for (int i = 0; i < M; i++) {
        int p, c;
        cin >> p >> c;
        ch[i] = {c, p - 1};
    }
    sort(ch.begin(), ch.end());
    vector<int> t(N - 1);
    {
        auto dfs = [&](auto dfs, int x, int p) -> void {
            for (int z : adj[x]) {
                auto [u, v] = edges[z];
                int y = x ^ u ^ v;
                if (y != p) {
                    t[z] = y;
                    dfs(dfs, y, x);
                }
            }
        };
        dfs(dfs, 0, -1);
    }
    for (int i = 0; i < N; i++) {
        for (int &j : adj[i]) {
            auto [x, y] = edges[j];
            j = i ^ x ^ y;
        }
    }
    vector<int> dep(N), par(N, -1), sz(N);
    auto init = [&](auto init, int x) -> void {
        if (par[x] != -1) {
            adj[x].erase(find(adj[x].begin(), adj[x].end(), par[x]));
        }
        sz[x] = 1;
        for (int &y : adj[x]) {
            par[y] = x;
            dep[y] = dep[x] + 1;
            init(init, y);
            sz[x] += sz[y];
            if (sz[y] > sz[adj[x][0]]) {
                swap(y, adj[x][0]);
            }
        }
    };
    init(init, 0);
    vector<int> top(N), in(N);
    int timer = 0;
    auto dfs = [&](auto dfs, int x) -> void {
        in[x] = timer++;
        for (int y : adj[x]) {
            top[y] = adj[x][0] == y ? top[x] : y;
            dfs(dfs, y);
        }
    };
    dfs(dfs, 0);
    vector<node*> q{bld(0, N)};
    for (int i = 0; i < M; i++) {
        auto [c, p] = ch[i];
        q.push_back(add(q.back(), 0, N, in[t[p]], c));
    }
    vector<int> S(Q), T(Q), X(Q);
    vector<ll> Y(Q);
    for (int i = 0; i < Q; i++) {
        cin >> S[i] >> T[i] >> X[i] >> Y[i];
        S[i]--, T[i]--;
    }
    vector<int> a(Q);
    for (int i = 0; i < Q; i++) {
        int lo = 0, hi = M;
        while (lo < hi) {
            int mi = (lo + hi + 1) / 2;
            int x = S[i], y = T[i]; ll s = 0;
            while (top[x] != top[y]) {
                if (dep[top[x]] < dep[top[y]]) {
                    swap(x, y);
                }
                s += qry(q[mi], 0, N, in[top[x]], in[x] + 1);
                x = par[top[x]];
            }
            if (dep[x] < dep[y]) {
                swap(x, y);
            }
            s += qry(q[mi], 0, N, in[y] + 1, in[x] + 1);
            if (s <= Y[i]) {
                lo = mi;
            } else {
                hi = mi - 1;
            }
        }
        a[i] = lo;
    }
    vector<ll> bit(N + 1);
    auto add = [&](int i, int v) {
        for (i++; i <= N; i += i & -i) {
            bit[i] += v;
        }
    };
    auto sum = [&](int i) {
        ll s = 0;
        for (; i; i -= i & -i) {
            s += bit[i];
        }
        return s;
    };
    auto get = [&](int x, int y) {
        ll s = 0;
        while (top[x] != top[y]) {
            if (dep[top[x]] < dep[top[y]]) {
                swap(x, y);
            }
            s += sum(in[x] + 1) - sum(in[top[x]]);
            x = par[top[x]];
        }
        if (dep[x] < dep[y]) {
            swap(x, y);
        }
        s += sum(in[x] + 1) - sum(in[y] + 1);
        return s;
    };
    vector<ll> ans(Q);
    vector<vector<int>> f(M + 1);
    for (int i = 0; i < Q; i++) {
        f[a[i]].push_back(i);
    }
    bit.assign(N + 1, 0);
    for (int i = M; i >= 0; i--) {
        if (i < M) {
            auto [c, p] = ch[i];
            add(in[t[p]], 1);
        }
        for (int j : f[i]) {
            ans[j] = max(-1LL, X[j] - get(S[j], T[j]));
        }
    }
    for (int i = 0; i < Q; i++) {
        cout << ans[i] << "\n";
    }
    return 6/22;
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 7 ms 1484 KB Output is correct
6 Correct 12 ms 1460 KB Output is correct
7 Correct 10 ms 1188 KB Output is correct
8 Correct 10 ms 1620 KB Output is correct
9 Correct 10 ms 1532 KB Output is correct
10 Correct 10 ms 1620 KB Output is correct
11 Correct 10 ms 1620 KB Output is correct
12 Correct 10 ms 1620 KB Output is correct
13 Correct 6 ms 1748 KB Output is correct
14 Correct 6 ms 1748 KB Output is correct
15 Correct 7 ms 1620 KB Output is correct
16 Correct 8 ms 1616 KB Output is correct
17 Correct 8 ms 1580 KB Output is correct
18 Correct 8 ms 1620 KB Output is correct
19 Correct 7 ms 1620 KB Output is correct
20 Correct 7 ms 1588 KB Output is correct
21 Correct 6 ms 1612 KB Output is correct
22 Correct 6 ms 1620 KB Output is correct
23 Correct 10 ms 1536 KB Output is correct
24 Correct 10 ms 1544 KB Output is correct
25 Correct 10 ms 1544 KB Output is correct
26 Correct 7 ms 1540 KB Output is correct
27 Correct 7 ms 1532 KB Output is correct
28 Correct 10 ms 1532 KB Output is correct
29 Correct 5 ms 1620 KB Output is correct
30 Correct 10 ms 1540 KB Output is correct
31 Correct 11 ms 1544 KB Output is correct
32 Correct 10 ms 1576 KB Output is correct
33 Correct 6 ms 1868 KB Output is correct
34 Correct 5 ms 1800 KB Output is correct
35 Correct 5 ms 1876 KB Output is correct

Subtask #2
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 10 ms 1620 KB Output is correct
3 Correct 12 ms 1620 KB Output is correct
4 Correct 10 ms 1544 KB Output is correct
5 Correct 1433 ms 76388 KB Output is correct
6 Correct 2000 ms 67192 KB Output is correct
7 Correct 1758 ms 60300 KB Output is correct
8 Correct 1325 ms 57596 KB Output is correct
9 Correct 1339 ms 60276 KB Output is correct
10 Correct 2388 ms 85016 KB Output is correct
11 Correct 2382 ms 85044 KB Output is correct
12 Correct 2375 ms 85060 KB Output is correct
13 Correct 2584 ms 85036 KB Output is correct
14 Correct 2349 ms 85036 KB Output is correct
15 Correct 1114 ms 96588 KB Output is correct
16 Correct 1143 ms 97280 KB Output is correct
17 Correct 1151 ms 96048 KB Output is correct
18 Correct 2375 ms 85612 KB Output is correct
19 Correct 2459 ms 85660 KB Output is correct
20 Correct 2475 ms 85776 KB Output is correct
21 Correct 773 ms 85324 KB Output is correct
22 Correct 787 ms 85420 KB Output is correct
23 Correct 797 ms 85380 KB Output is correct
24 Correct 789 ms 85412 KB Output is correct
25 Correct 1623 ms 86304 KB Output is correct
26 Correct 1743 ms 84648 KB Output is correct
27 Correct 1742 ms 84636 KB Output is correct
28 Correct 1071 ms 84432 KB Output is correct
29 Correct 937 ms 84428 KB Output is correct
30 Correct 1588 ms 84572 KB Output is correct
31 Correct 1439 ms 84588 KB Output is correct

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 320 KB Output is correct
2 Correct 5 ms 1756 KB Output is correct
3 Correct 6 ms 1864 KB Output is correct
4 Correct 6 ms 1868 KB Output is correct
5 Correct 645 ms 71812 KB Output is correct
6 Correct 579 ms 62932 KB Output is correct
7 Correct 956 ms 76784 KB Output is correct
8 Correct 1237 ms 97476 KB Output is correct
9 Correct 1298 ms 97504 KB Output is correct
10 Correct 1293 ms 97472 KB Output is correct
11 Correct 990 ms 97844 KB Output is correct
12 Correct 994 ms 97792 KB Output is correct
13 Correct 992 ms 96288 KB Output is correct
14 Correct 629 ms 96480 KB Output is correct
15 Correct 520 ms 96228 KB Output is correct
16 Correct 698 ms 96764 KB Output is correct
17 Correct 731 ms 96560 KB Output is correct

Subtask #4
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 7 ms 1484 KB Output is correct
6 Correct 12 ms 1460 KB Output is correct
7 Correct 10 ms 1188 KB Output is correct
8 Correct 10 ms 1620 KB Output is correct
9 Correct 10 ms 1532 KB Output is correct
10 Correct 10 ms 1620 KB Output is correct
11 Correct 10 ms 1620 KB Output is correct
12 Correct 10 ms 1620 KB Output is correct
13 Correct 6 ms 1748 KB Output is correct
14 Correct 6 ms 1748 KB Output is correct
15 Correct 7 ms 1620 KB Output is correct
16 Correct 8 ms 1616 KB Output is correct
17 Correct 8 ms 1580 KB Output is correct
18 Correct 8 ms 1620 KB Output is correct
19 Correct 7 ms 1620 KB Output is correct
20 Correct 7 ms 1588 KB Output is correct
21 Correct 6 ms 1612 KB Output is correct
22 Correct 6 ms 1620 KB Output is correct
23 Correct 10 ms 1536 KB Output is correct
24 Correct 10 ms 1544 KB Output is correct
25 Correct 10 ms 1544 KB Output is correct
26 Correct 7 ms 1540 KB Output is correct
27 Correct 7 ms 1532 KB Output is correct
28 Correct 10 ms 1532 KB Output is correct
29 Correct 5 ms 1620 KB Output is correct
30 Correct 10 ms 1540 KB Output is correct
31 Correct 11 ms 1544 KB Output is correct
32 Correct 10 ms 1576 KB Output is correct
33 Correct 6 ms 1868 KB Output is correct
34 Correct 5 ms 1800 KB Output is correct
35 Correct 5 ms 1876 KB Output is correct
36 Correct 1 ms 212 KB Output is correct
37 Correct 10 ms 1620 KB Output is correct
38 Correct 12 ms 1620 KB Output is correct
39 Correct 10 ms 1544 KB Output is correct
40 Correct 1433 ms 76388 KB Output is correct
41 Correct 2000 ms 67192 KB Output is correct
42 Correct 1758 ms 60300 KB Output is correct
43 Correct 1325 ms 57596 KB Output is correct
44 Correct 1339 ms 60276 KB Output is correct
45 Correct 2388 ms 85016 KB Output is correct
46 Correct 2382 ms 85044 KB Output is correct
47 Correct 2375 ms 85060 KB Output is correct
48 Correct 2584 ms 85036 KB Output is correct
49 Correct 2349 ms 85036 KB Output is correct
50 Correct 1114 ms 96588 KB Output is correct
51 Correct 1143 ms 97280 KB Output is correct
52 Correct 1151 ms 96048 KB Output is correct
53 Correct 2375 ms 85612 KB Output is correct
54 Correct 2459 ms 85660 KB Output is correct
55 Correct 2475 ms 85776 KB Output is correct
56 Correct 773 ms 85324 KB Output is correct
57 Correct 787 ms 85420 KB Output is correct
58 Correct 797 ms 85380 KB Output is correct
59 Correct 789 ms 85412 KB Output is correct
60 Correct 1623 ms 86304 KB Output is correct
61 Correct 1743 ms 84648 KB Output is correct
62 Correct 1742 ms 84636 KB Output is correct
63 Correct 1071 ms 84432 KB Output is correct
64 Correct 937 ms 84428 KB Output is correct
65 Correct 1588 ms 84572 KB Output is correct
66 Correct 1439 ms 84588 KB Output is correct
67 Correct 0 ms 320 KB Output is correct
68 Correct 5 ms 1756 KB Output is correct
69 Correct 6 ms 1864 KB Output is correct
70 Correct 6 ms 1868 KB Output is correct
71 Correct 645 ms 71812 KB Output is correct
72 Correct 579 ms 62932 KB Output is correct
73 Correct 956 ms 76784 KB Output is correct
74 Correct 1237 ms 97476 KB Output is correct
75 Correct 1298 ms 97504 KB Output is correct
76 Correct 1293 ms 97472 KB Output is correct
77 Correct 990 ms 97844 KB Output is correct
78 Correct 994 ms 97792 KB Output is correct
79 Correct 992 ms 96288 KB Output is correct
80 Correct 629 ms 96480 KB Output is correct
81 Correct 520 ms 96228 KB Output is correct
82 Correct 698 ms 96764 KB Output is correct
83 Correct 731 ms 96560 KB Output is correct
84 Correct 1617 ms 75156 KB Output is correct
85 Correct 1883 ms 64244 KB Output is correct
86 Correct 1583 ms 49012 KB Output is correct
87 Correct 2771 ms 84972 KB Output is correct
88 Correct 2852 ms 84984 KB Output is correct
89 Correct 2957 ms 84976 KB Output is correct
90 Correct 2892 ms 84964 KB Output is correct
91 Correct 2739 ms 84972 KB Output is correct
92 Correct 1543 ms 93328 KB Output is correct
93 Correct 1466 ms 95688 KB Output is correct
94 Correct 2819 ms 85808 KB Output is correct
95 Correct 2895 ms 85748 KB Output is correct
96 Correct 2759 ms 85732 KB Output is correct
97 Correct 2896 ms 85696 KB Output is correct
98 Correct 1468 ms 85308 KB Output is correct
99 Correct 1390 ms 85256 KB Output is correct
100 Correct 1405 ms 85360 KB Output is correct
101 Correct 1372 ms 85360 KB Output is correct
102 Correct 1944 ms 86168 KB Output is correct
103 Correct 2060 ms 84588 KB Output is correct
104 Correct 2049 ms 84588 KB Output is correct
105 Correct 1113 ms 84544 KB Output is correct
106 Correct 1493 ms 84500 KB Output is correct
107 Correct 1500 ms 84416 KB Output is correct
108 Correct 1516 ms 84448 KB Output is correct