oj.uz

Submission #868427

# Submission time Handle Problem Language Result Execution time Memory
868427 2023-10-31T13:13:29 Z t6twotwo Two Currencies (JOI23_currencies) C++17
100 / 100
 3747 ms 162192 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template <class S, S (*f)(S, S), S e>
struct PST {
    struct T {
        T *l, *r; S s;
        T() : s() {l = r = nullptr;}
        T(const S &v) : s(v) {l = r = nullptr;}
        T(T *t) : l(t->l), r(t->r), s(t->s) {}
        T(T *a, T *b) : l(a), r(b), s() {
            if (l) s = f(s, l->s);
            if (r) s = f(s, r->s);
        }
    };
    int n;
    vector<T*> rts;
    PST(int m) : PST(vector<S>(m, e)) {
    }
    PST(const vector<S> &a) : n(a.size()) {
        function<T*(int, int)> bld = [&](int l, int r) {
            if (l + 1 == r) {
                return new T(a[l]);
            }
            int m = (l + r) / 2;
            return new T(bld(l, m), bld(m, r));
        };
        rts.push_back(bld(0, n));
    }
    T* set(T *i, int l, int r, int p, const S &v) {
        if (l + 1 == r) {
            return new T(v);
        }
        int m = (l + r) / 2;
        if (p < m) {
            return new T(set(i->l, l, m, p, v), i->r);
        } else {
            return new T(i->l, set(i->r, m, r, p, v));
        }
    }
    T* upd(T *i, int l, int r, int p, const S &v) {
        if (l + 1 == r) {
            return new T(f(i->s, v));
        }
        int m = (l + r) / 2;
        if (p < m) {
            return new T(upd(i->l, l, m, p, v), i->r);
        } else {
            return new T(i->l, upd(i->r, m, r, p, v));
        }
    }
    S qry(T *i, int l, int r, int L, int R) {
        if (R <= l || r <= L) {
            return e;
        }
        if (L <= l && r <= R) {
            return i->s;
        }
        int m = (l + r) / 2;
        return f(qry(i->l, l, m, L, R), qry(i->r, m, r, L, R));
    }
    int lst() {
        return rts.size() - 1;
    }
    int cpy(int k) {
        rts.push_back(new T(rts[k]));
        return rts.size() - 1;
    }
    void set(int k, int i, const S &v) {
        rts[k] = set(rts[k], 0, n, i, v);
    }
    void upd(int k, int i, const S &v) {
        rts[k] = upd(rts[k], 0, n, i, v);
    }
    S qry(int k, int l, int r) {
        return qry(rts[k], 0, n, l, r);
    }
};
ll F(ll x, ll y) {
    return x + y;
}
struct HLD {
    int n, timer;
    vector<int> sz, dep, par, top, pos;
    vector<vector<int>> adj;
    HLD(int n) : n(n) {
        sz.resize(n);
        dep.resize(n);
        top.resize(n);
        pos.resize(n);
        adj.resize(n);
        par.resize(n, -1);
    }
    void add_edge(int x, int y) {
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    void init(int x) {
        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(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() {
        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, bool e, 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);
    }
    for (int i = 0; i < N; i++) {
        for (int &j : adj[i]) {
            auto [x, y] = edges[j];
            j = i ^ x ^ y;
        }
    }
    HLD hld(N);
    for (int i = 0; i < N; i++) {
        for (int j : adj[i]) {
            if (i < j) {
                hld.add_edge(i, j);
            }
        }
    }
    hld.build();
    PST<ll, F, 0> q(N);
    for (int i = 0; i < M; i++) {
        auto [c, p] = ch[i];
        q.upd(q.cpy(q.lst()), hld.pos[t[p]], c);
    }
    auto get = [&](int x, int y, int z) -> ll {
        ll s = 0;
        hld.path(x, y, 1, [&](int l, int r) {
            s += q.qry(z, l, r);
        });
        return s;
    };
    vector<int> S(Q), T(Q), X(Q), a(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]--;
        int lo = 0, hi = M;
        while (lo < hi) {
            int mi = (lo + hi + 1) / 2;
            if (get(S[i], T[i], mi) <= Y[i]) {
                lo = mi;
            } else {
                hi = mi - 1;
            }
        }
        a[i] = lo;
    }
    vector<ll> ans(Q);
    vector<vector<int>> f(M + 1);
    for (int i = 0; i < Q; i++) {
        f[a[i]].push_back(i);
    }
    q = PST<ll, F, 0>(N);
    for (int i = M; i >= 0; i--) {
        if (i < M) {
            auto [c, p] = ch[i];
            q.upd(q.cpy(q.lst()), hld.pos[t[p]], 1);
        }
        for (int j : f[i]) {
            ans[j] = max(-1LL, X[j] - get(S[j], T[j], q.lst()));
        }
    }
    for (int i = 0; i < Q; i++) {
        cout << ans[i] << "\n";
    }
    return 6/22;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 8 ms 2396 KB Output is correct
6 Correct 11 ms 2392 KB Output is correct
7 Correct 9 ms 1880 KB Output is correct
8 Correct 12 ms 2648 KB Output is correct
9 Correct 15 ms 2648 KB Output is correct
10 Correct 12 ms 2652 KB Output is correct
11 Correct 12 ms 2784 KB Output is correct
12 Correct 12 ms 2788 KB Output is correct
13 Correct 9 ms 2908 KB Output is correct
14 Correct 10 ms 2652 KB Output is correct
15 Correct 13 ms 2648 KB Output is correct
16 Correct 9 ms 2652 KB Output is correct
17 Correct 10 ms 2652 KB Output is correct
18 Correct 9 ms 2652 KB Output is correct
19 Correct 8 ms 2804 KB Output is correct
20 Correct 12 ms 2652 KB Output is correct
21 Correct 8 ms 2648 KB Output is correct
22 Correct 8 ms 2652 KB Output is correct
23 Correct 11 ms 2652 KB Output is correct
24 Correct 13 ms 2904 KB Output is correct
25 Correct 12 ms 2652 KB Output is correct
26 Correct 8 ms 2652 KB Output is correct
27 Correct 8 ms 2788 KB Output is correct
28 Correct 15 ms 2648 KB Output is correct
29 Correct 6 ms 2652 KB Output is correct
30 Correct 12 ms 2652 KB Output is correct
31 Correct 12 ms 2652 KB Output is correct
32 Correct 13 ms 2652 KB Output is correct
33 Correct 8 ms 2900 KB Output is correct
34 Correct 8 ms 3160 KB Output is correct
35 Correct 9 ms 2904 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 12 ms 2652 KB Output is correct
3 Correct 12 ms 2788 KB Output is correct
4 Correct 16 ms 2788 KB Output is correct
5 Correct 1996 ms 138600 KB Output is correct
6 Correct 2629 ms 118388 KB Output is correct
7 Correct 2333 ms 105176 KB Output is correct
8 Correct 1762 ms 101500 KB Output is correct
9 Correct 1684 ms 107696 KB Output is correct
10 Correct 3188 ms 152784 KB Output is correct
11 Correct 3449 ms 152608 KB Output is correct
12 Correct 3394 ms 152572 KB Output is correct
13 Correct 3243 ms 152508 KB Output is correct
14 Correct 3396 ms 152580 KB Output is correct
15 Correct 2008 ms 160476 KB Output is correct
16 Correct 1834 ms 161264 KB Output is correct
17 Correct 1897 ms 160380 KB Output is correct
18 Correct 3201 ms 152712 KB Output is correct
19 Correct 3156 ms 152740 KB Output is correct
20 Correct 3057 ms 152744 KB Output is correct
21 Correct 1410 ms 153644 KB Output is correct
22 Correct 1594 ms 153628 KB Output is correct
23 Correct 1466 ms 153704 KB Output is correct
24 Correct 1672 ms 153712 KB Output is correct
25 Correct 2079 ms 150980 KB Output is correct
26 Correct 2298 ms 154028 KB Output is correct
27 Correct 2065 ms 154020 KB Output is correct
28 Correct 1133 ms 152060 KB Output is correct
29 Correct 1150 ms 152108 KB Output is correct
30 Correct 1832 ms 152032 KB Output is correct
31 Correct 1647 ms 152188 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 9 ms 2904 KB Output is correct
3 Correct 9 ms 2904 KB Output is correct
4 Correct 7 ms 2908 KB Output is correct
5 Correct 910 ms 114868 KB Output is correct
6 Correct 892 ms 97524 KB Output is correct
7 Correct 1327 ms 130620 KB Output is correct
8 Correct 1821 ms 161272 KB Output is correct
9 Correct 1808 ms 161444 KB Output is correct
10 Correct 1782 ms 161708 KB Output is correct
11 Correct 1300 ms 162192 KB Output is correct
12 Correct 1312 ms 162024 KB Output is correct
13 Correct 1331 ms 159084 KB Output is correct
14 Correct 942 ms 160172 KB Output is correct
15 Correct 738 ms 159924 KB Output is correct
16 Correct 1082 ms 160428 KB Output is correct
17 Correct 1012 ms 160312 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 1 ms 596 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 8 ms 2396 KB Output is correct
6 Correct 11 ms 2392 KB Output is correct
7 Correct 9 ms 1880 KB Output is correct
8 Correct 12 ms 2648 KB Output is correct
9 Correct 15 ms 2648 KB Output is correct
10 Correct 12 ms 2652 KB Output is correct
11 Correct 12 ms 2784 KB Output is correct
12 Correct 12 ms 2788 KB Output is correct
13 Correct 9 ms 2908 KB Output is correct
14 Correct 10 ms 2652 KB Output is correct
15 Correct 13 ms 2648 KB Output is correct
16 Correct 9 ms 2652 KB Output is correct
17 Correct 10 ms 2652 KB Output is correct
18 Correct 9 ms 2652 KB Output is correct
19 Correct 8 ms 2804 KB Output is correct
20 Correct 12 ms 2652 KB Output is correct
21 Correct 8 ms 2648 KB Output is correct
22 Correct 8 ms 2652 KB Output is correct
23 Correct 11 ms 2652 KB Output is correct
24 Correct 13 ms 2904 KB Output is correct
25 Correct 12 ms 2652 KB Output is correct
26 Correct 8 ms 2652 KB Output is correct
27 Correct 8 ms 2788 KB Output is correct
28 Correct 15 ms 2648 KB Output is correct
29 Correct 6 ms 2652 KB Output is correct
30 Correct 12 ms 2652 KB Output is correct
31 Correct 12 ms 2652 KB Output is correct
32 Correct 13 ms 2652 KB Output is correct
33 Correct 8 ms 2900 KB Output is correct
34 Correct 8 ms 3160 KB Output is correct
35 Correct 9 ms 2904 KB Output is correct
36 Correct 1 ms 344 KB Output is correct
37 Correct 12 ms 2652 KB Output is correct
38 Correct 12 ms 2788 KB Output is correct
39 Correct 16 ms 2788 KB Output is correct
40 Correct 1996 ms 138600 KB Output is correct
41 Correct 2629 ms 118388 KB Output is correct
42 Correct 2333 ms 105176 KB Output is correct
43 Correct 1762 ms 101500 KB Output is correct
44 Correct 1684 ms 107696 KB Output is correct
45 Correct 3188 ms 152784 KB Output is correct
46 Correct 3449 ms 152608 KB Output is correct
47 Correct 3394 ms 152572 KB Output is correct
48 Correct 3243 ms 152508 KB Output is correct
49 Correct 3396 ms 152580 KB Output is correct
50 Correct 2008 ms 160476 KB Output is correct
51 Correct 1834 ms 161264 KB Output is correct
52 Correct 1897 ms 160380 KB Output is correct
53 Correct 3201 ms 152712 KB Output is correct
54 Correct 3156 ms 152740 KB Output is correct
55 Correct 3057 ms 152744 KB Output is correct
56 Correct 1410 ms 153644 KB Output is correct
57 Correct 1594 ms 153628 KB Output is correct
58 Correct 1466 ms 153704 KB Output is correct
59 Correct 1672 ms 153712 KB Output is correct
60 Correct 2079 ms 150980 KB Output is correct
61 Correct 2298 ms 154028 KB Output is correct
62 Correct 2065 ms 154020 KB Output is correct
63 Correct 1133 ms 152060 KB Output is correct
64 Correct 1150 ms 152108 KB Output is correct
65 Correct 1832 ms 152032 KB Output is correct
66 Correct 1647 ms 152188 KB Output is correct
67 Correct 1 ms 344 KB Output is correct
68 Correct 9 ms 2904 KB Output is correct
69 Correct 9 ms 2904 KB Output is correct
70 Correct 7 ms 2908 KB Output is correct
71 Correct 910 ms 114868 KB Output is correct
72 Correct 892 ms 97524 KB Output is correct
73 Correct 1327 ms 130620 KB Output is correct
74 Correct 1821 ms 161272 KB Output is correct
75 Correct 1808 ms 161444 KB Output is correct
76 Correct 1782 ms 161708 KB Output is correct
77 Correct 1300 ms 162192 KB Output is correct
78 Correct 1312 ms 162024 KB Output is correct
79 Correct 1331 ms 159084 KB Output is correct
80 Correct 942 ms 160172 KB Output is correct
81 Correct 738 ms 159924 KB Output is correct
82 Correct 1082 ms 160428 KB Output is correct
83 Correct 1012 ms 160312 KB Output is correct
84 Correct 2184 ms 136852 KB Output is correct
85 Correct 2282 ms 115860 KB Output is correct
86 Correct 1823 ms 85568 KB Output is correct
87 Correct 3641 ms 152672 KB Output is correct
88 Correct 3461 ms 152568 KB Output is correct
89 Correct 3357 ms 152572 KB Output is correct
90 Correct 3747 ms 152576 KB Output is correct
91 Correct 3624 ms 153008 KB Output is correct
92 Correct 2043 ms 158248 KB Output is correct
93 Correct 2039 ms 159916 KB Output is correct
94 Correct 3441 ms 152792 KB Output is correct
95 Correct 3681 ms 152792 KB Output is correct
96 Correct 3530 ms 152784 KB Output is correct
97 Correct 3618 ms 152764 KB Output is correct
98 Correct 1930 ms 153644 KB Output is correct
99 Correct 1866 ms 153652 KB Output is correct
100 Correct 1832 ms 153636 KB Output is correct
101 Correct 1810 ms 153636 KB Output is correct
102 Correct 2352 ms 150964 KB Output is correct
103 Correct 2283 ms 150992 KB Output is correct
104 Correct 2178 ms 154080 KB Output is correct
105 Correct 1211 ms 152080 KB Output is correct
106 Correct 1603 ms 152328 KB Output is correct
107 Correct 1699 ms 152104 KB Output is correct
108 Correct 1567 ms 152056 KB Output is correct