oj.uz

Submission #868468

# Submission time Handle Problem Language Result Execution time Memory
868468 2023-10-31T13:53:38 Z t6twotwo Two Currencies (JOI23_currencies) C++17
100 / 100
 900 ms 33572 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct HLD {
    bool e;
    int n, timer;
    vector<int> sz, dep, par, top, pos;
    vector<vector<int>> adj;
    HLD(int m, bool edge) : n(m), e(edge) {
        sz.resize(n);
        dep.resize(n);
        top.resize(n);
        pos.resize(n);
        adj.resize(n);
        par.resize(n);
    }
    void add_edge(int x, int y) {
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    void init(int x) {
        sz[x] = 1;
        for (int &y : adj[x]) {
            dep[y] = dep[x] + 1;
            adj[y].erase(find(adj[y].begin(), adj[y].end(), par[y] = x));
            init(y);
            sz[x] += sz[y];
            if (sz[y] > sz[adj[x][0]]) {
                swap(y, adj[x][0]);
            }
        }
    }
    void dfs(int x) {
        pos[x] = timer++;
        for (int y : adj[x]) {
            top[y] = y == adj[x][0] ? top[x] : y;
            dfs(y);
        }
    }
    void build() {
        par[0] = -1; init(0);
        timer = 0; dfs(0);
    }
    int lca(int x, int y) {
        for (; top[x] != top[y]; x = par[top[x]]) {
            if (dep[top[x]] < dep[top[y]]) {
                swap(x, y);
            }
        }
        return dep[x] < dep[y] ? x : y;
    }
    template <class T>
    void path(int x, int y, T f) {
        for (; top[x] != top[y]; x = par[top[x]]) {
            if (dep[top[x]] < dep[top[y]]) {
                swap(x, y);
            }
            f(pos[top[x]], pos[x] + 1);
        }
        if (dep[x] > dep[y]) {
            swap(x, y);
        }
        f(pos[x] + e, pos[y] + 1);
    }
};
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);
    }
    HLD hld(N, 1);
    for (int i = 0; i < N; i++) {
        for (int &j : adj[i]) {
            auto [x, y] = edges[j];
            j = i ^ x ^ y;
            if (j < i) {
                hld.add_edge(i, j);
            }
        }
    }
    hld.build();
    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]--;
        if (S[i] > T[i]) {
            swap(S[i], T[i]);
        }
    }
    vector<int> lo(Q), hi(Q, M);
    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;
        hld.path(x, y, [&](int l, int r) {
            s += sum(r) - sum(l);
        });
        return s;
    };
    for (int z = 0; z < 20; z++) {
        vector<int> mi(Q);
        vector<vector<int>> f(M);
        for (int i = 0; i < Q; i++) {
            if (lo[i] != hi[i]) {
                mi[i] = (lo[i] + hi[i] + 1) / 2;
                f[mi[i] - 1].push_back(i);
            }
        }
        bit.assign(N + 1, 0);
        for (int i = 0; i < M; i++) {
            auto [c, p] = ch[i];
            add(hld.pos[t[p]], c);
            for (int j : f[i]) {
                if (get(S[j], T[j]) <= Y[j]) {
                    lo[j] = i + 1;
                } else {
                    hi[j] = i;
                }
            }
        }
    }
    vector<ll> ans(Q);
    vector<vector<int>> f(M + 1);
    for (int i = 0; i < Q; i++) {
        f[lo[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(hld.pos[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;
}

Compilation message

currencies.cpp: In constructor 'HLD::HLD(int, bool)':
currencies.cpp:6:9: warning: 'HLD::n' will be initialized after [-Wreorder]
    6 |     int n, timer;
      |         ^
currencies.cpp:5:10: warning:   'bool HLD::e' [-Wreorder]
    5 |     bool e;
      |          ^
currencies.cpp:9:5: warning:   when initialized here [-Wreorder]
    9 |     HLD(int m, bool edge) : n(m), e(edge) {
      |     ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 5 ms 860 KB Output is correct
6 Correct 6 ms 860 KB Output is correct
7 Correct 5 ms 604 KB Output is correct
8 Correct 7 ms 916 KB Output is correct
9 Correct 7 ms 860 KB Output is correct
10 Correct 7 ms 856 KB Output is correct
11 Correct 7 ms 860 KB Output is correct
12 Correct 7 ms 860 KB Output is correct
13 Correct 4 ms 1116 KB Output is correct
14 Correct 5 ms 1004 KB Output is correct
15 Correct 5 ms 968 KB Output is correct
16 Correct 7 ms 860 KB Output is correct
17 Correct 5 ms 860 KB Output is correct
18 Correct 5 ms 860 KB Output is correct
19 Correct 4 ms 860 KB Output is correct
20 Correct 4 ms 860 KB Output is correct
21 Correct 4 ms 856 KB Output is correct
22 Correct 4 ms 860 KB Output is correct
23 Correct 6 ms 860 KB Output is correct
24 Correct 6 ms 860 KB Output is correct
25 Correct 6 ms 908 KB Output is correct
26 Correct 4 ms 860 KB Output is correct
27 Correct 4 ms 860 KB Output is correct
28 Correct 4 ms 860 KB Output is correct
29 Correct 3 ms 860 KB Output is correct
30 Correct 7 ms 860 KB Output is correct
31 Correct 7 ms 860 KB Output is correct
32 Correct 7 ms 860 KB Output is correct
33 Correct 4 ms 1116 KB Output is correct
34 Correct 5 ms 1116 KB Output is correct
35 Correct 4 ms 1116 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 7 ms 896 KB Output is correct
3 Correct 7 ms 860 KB Output is correct
4 Correct 7 ms 908 KB Output is correct
5 Correct 577 ms 22908 KB Output is correct
6 Correct 767 ms 19460 KB Output is correct
7 Correct 719 ms 20252 KB Output is correct
8 Correct 582 ms 19700 KB Output is correct
9 Correct 528 ms 19636 KB Output is correct
10 Correct 887 ms 25184 KB Output is correct
11 Correct 858 ms 25336 KB Output is correct
12 Correct 872 ms 25492 KB Output is correct
13 Correct 858 ms 25312 KB Output is correct
14 Correct 849 ms 25488 KB Output is correct
15 Correct 332 ms 32764 KB Output is correct
16 Correct 332 ms 33156 KB Output is correct
17 Correct 328 ms 32080 KB Output is correct
18 Correct 618 ms 25372 KB Output is correct
19 Correct 621 ms 25488 KB Output is correct
20 Correct 668 ms 25232 KB Output is correct
21 Correct 357 ms 25868 KB Output is correct
22 Correct 344 ms 25832 KB Output is correct
23 Correct 350 ms 26384 KB Output is correct
24 Correct 336 ms 25868 KB Output is correct
25 Correct 651 ms 25596 KB Output is correct
26 Correct 678 ms 25328 KB Output is correct
27 Correct 606 ms 25428 KB Output is correct
28 Correct 311 ms 24324 KB Output is correct
29 Correct 321 ms 24376 KB Output is correct
30 Correct 415 ms 24672 KB Output is correct
31 Correct 400 ms 24656 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 4 ms 1116 KB Output is correct
3 Correct 4 ms 1116 KB Output is correct
4 Correct 4 ms 1116 KB Output is correct
5 Correct 209 ms 28848 KB Output is correct
6 Correct 195 ms 27216 KB Output is correct
7 Correct 256 ms 22092 KB Output is correct
8 Correct 324 ms 33420 KB Output is correct
9 Correct 334 ms 33336 KB Output is correct
10 Correct 321 ms 33168 KB Output is correct
11 Correct 281 ms 33572 KB Output is correct
12 Correct 297 ms 33372 KB Output is correct
13 Correct 276 ms 33172 KB Output is correct
14 Correct 259 ms 33164 KB Output is correct
15 Correct 244 ms 33188 KB Output is correct
16 Correct 278 ms 33072 KB Output is correct
17 Correct 308 ms 33124 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 5 ms 860 KB Output is correct
6 Correct 6 ms 860 KB Output is correct
7 Correct 5 ms 604 KB Output is correct
8 Correct 7 ms 916 KB Output is correct
9 Correct 7 ms 860 KB Output is correct
10 Correct 7 ms 856 KB Output is correct
11 Correct 7 ms 860 KB Output is correct
12 Correct 7 ms 860 KB Output is correct
13 Correct 4 ms 1116 KB Output is correct
14 Correct 5 ms 1004 KB Output is correct
15 Correct 5 ms 968 KB Output is correct
16 Correct 7 ms 860 KB Output is correct
17 Correct 5 ms 860 KB Output is correct
18 Correct 5 ms 860 KB Output is correct
19 Correct 4 ms 860 KB Output is correct
20 Correct 4 ms 860 KB Output is correct
21 Correct 4 ms 856 KB Output is correct
22 Correct 4 ms 860 KB Output is correct
23 Correct 6 ms 860 KB Output is correct
24 Correct 6 ms 860 KB Output is correct
25 Correct 6 ms 908 KB Output is correct
26 Correct 4 ms 860 KB Output is correct
27 Correct 4 ms 860 KB Output is correct
28 Correct 4 ms 860 KB Output is correct
29 Correct 3 ms 860 KB Output is correct
30 Correct 7 ms 860 KB Output is correct
31 Correct 7 ms 860 KB Output is correct
32 Correct 7 ms 860 KB Output is correct
33 Correct 4 ms 1116 KB Output is correct
34 Correct 5 ms 1116 KB Output is correct
35 Correct 4 ms 1116 KB Output is correct
36 Correct 0 ms 348 KB Output is correct
37 Correct 7 ms 896 KB Output is correct
38 Correct 7 ms 860 KB Output is correct
39 Correct 7 ms 908 KB Output is correct
40 Correct 577 ms 22908 KB Output is correct
41 Correct 767 ms 19460 KB Output is correct
42 Correct 719 ms 20252 KB Output is correct
43 Correct 582 ms 19700 KB Output is correct
44 Correct 528 ms 19636 KB Output is correct
45 Correct 887 ms 25184 KB Output is correct
46 Correct 858 ms 25336 KB Output is correct
47 Correct 872 ms 25492 KB Output is correct
48 Correct 858 ms 25312 KB Output is correct
49 Correct 849 ms 25488 KB Output is correct
50 Correct 332 ms 32764 KB Output is correct
51 Correct 332 ms 33156 KB Output is correct
52 Correct 328 ms 32080 KB Output is correct
53 Correct 618 ms 25372 KB Output is correct
54 Correct 621 ms 25488 KB Output is correct
55 Correct 668 ms 25232 KB Output is correct
56 Correct 357 ms 25868 KB Output is correct
57 Correct 344 ms 25832 KB Output is correct
58 Correct 350 ms 26384 KB Output is correct
59 Correct 336 ms 25868 KB Output is correct
60 Correct 651 ms 25596 KB Output is correct
61 Correct 678 ms 25328 KB Output is correct
62 Correct 606 ms 25428 KB Output is correct
63 Correct 311 ms 24324 KB Output is correct
64 Correct 321 ms 24376 KB Output is correct
65 Correct 415 ms 24672 KB Output is correct
66 Correct 400 ms 24656 KB Output is correct
67 Correct 0 ms 348 KB Output is correct
68 Correct 4 ms 1116 KB Output is correct
69 Correct 4 ms 1116 KB Output is correct
70 Correct 4 ms 1116 KB Output is correct
71 Correct 209 ms 28848 KB Output is correct
72 Correct 195 ms 27216 KB Output is correct
73 Correct 256 ms 22092 KB Output is correct
74 Correct 324 ms 33420 KB Output is correct
75 Correct 334 ms 33336 KB Output is correct
76 Correct 321 ms 33168 KB Output is correct
77 Correct 281 ms 33572 KB Output is correct
78 Correct 297 ms 33372 KB Output is correct
79 Correct 276 ms 33172 KB Output is correct
80 Correct 259 ms 33164 KB Output is correct
81 Correct 244 ms 33188 KB Output is correct
82 Correct 278 ms 33072 KB Output is correct
83 Correct 308 ms 33124 KB Output is correct
84 Correct 609 ms 20924 KB Output is correct
85 Correct 622 ms 16516 KB Output is correct
86 Correct 574 ms 14804 KB Output is correct
87 Correct 889 ms 25384 KB Output is correct
88 Correct 891 ms 25172 KB Output is correct
89 Correct 888 ms 25232 KB Output is correct
90 Correct 890 ms 25604 KB Output is correct
91 Correct 900 ms 25188 KB Output is correct
92 Correct 371 ms 30348 KB Output is correct
93 Correct 369 ms 31876 KB Output is correct
94 Correct 653 ms 25480 KB Output is correct
95 Correct 640 ms 25484 KB Output is correct
96 Correct 650 ms 25548 KB Output is correct
97 Correct 684 ms 25484 KB Output is correct
98 Correct 398 ms 25864 KB Output is correct
99 Correct 393 ms 25872 KB Output is correct
100 Correct 387 ms 25872 KB Output is correct
101 Correct 379 ms 25616 KB Output is correct
102 Correct 630 ms 25484 KB Output is correct
103 Correct 656 ms 25480 KB Output is correct
104 Correct 625 ms 25440 KB Output is correct
105 Correct 323 ms 24724 KB Output is correct
106 Correct 371 ms 24464 KB Output is correct
107 Correct 450 ms 24656 KB Output is correct
108 Correct 383 ms 24724 KB Output is correct