oj.uz

Submission #759054

# Submission time Handle Problem Language Result Execution time Memory
759054 2023-06-15T17:37:40 Z Desh03 Two Currencies (JOI23_currencies) C++17
100 / 100
 1429 ms 38020 KB 
#include <bits/stdc++.h>
using namespace std;

struct fenwick {
    vector<pair<long long, int>> fenw;
    int n;
    fenwick(int n_) : n(n_) {
        fenw.resize(n, {0, 0});
    }
    void upd(int i, int d, int d2) {
        for (; i < n; i |= i + 1) fenw[i].first += d, fenw[i].second += d2;
    }
    pair<long long, int> qry(int i) {
        pair<long long, int> s = {0, 0};
        for (; i >= 0; i = (i & (i + 1)) - 1) s.first += fenw[i].first, s.second += fenw[i].second;
        return s;
    }
};

vector<vector<int>> g, up;
vector<int> in, out, dep;
int t;
const int lg = 17;

void dfs(int u) {
    in[u] = t++;
    for (int i = 1; i < lg; i++) up[i][u] = up[i - 1][up[i - 1][u]];
    for (int v : g[u])
        if (v ^ up[0][u])
            up[0][v] = u, dep[v] = dep[u] + 1, dfs(v);
    out[u] = t;
}

int lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    int k = dep[u] - dep[v];
    for (int i = 0; i < lg; i++)
        if (k >> i & 1)
            u = up[i][u];
    if (u == v) return u;
    for (int i = lg - 1; i >= 0; i--)
        if (up[i][u] ^ up[i][v])
            u = up[i][u], v = up[i][v];
    return up[0][u];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, m, q, c = 0;
    cin >> n >> m >> q;
    up = vector<vector<int>> (lg, vector<int> (n)), g.resize(n), in.resize(n), out.resize(n), dep.resize(n);
    vector<pair<int, int>> e(n - 1);
    for (auto &[a, b] : e) {
        cin >> a >> b;
        --a, --b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    dfs(0);
    fenwick fen(n);
    for (auto &[a, b] : e)
        if (b == up[0][a])
            swap(a, b);
    vector<pair<int, int>> ck(m);
    for (auto &[c, p] : ck) cin >> p >> c, --p;
    sort(ck.begin(), ck.end());
    vector<vector<int>> v(m);
    vector<tuple<int, int, int, long long>> qr(q);
    vector<int> l(q), r(q, m - 1), ans(q);
    for (int i = 0; i < q; i++) {
        v[(m - 1) >> 1].push_back(i);
        auto &[s, t, x, y] = qr[i];
        cin >> s >> t >> x >> y, --s, --t;
    }
    for (int itr = 0; itr < lg; itr++) {
        for (int i = 0; i < m; i++) {
            auto [c, p] = ck[i];
            int b = e[p].second;
            fen.upd(in[b], c, 1);
            fen.upd(out[b], -c, -1);
            for (int id : v[i]) {
                auto [s, t, x, y] = qr[id];
                auto [s1, s2, s3] = make_tuple(fen.qry(in[s]), fen.qry(in[t]), fen.qry(in[lca(s, t)]));
                if (s1.first + s2.first - (s3.first << 1) > y) r[id] = i - 1;
                else ans[id] = s1.second + s2.second - (s3.second << 1), l[id] = i + 1;
                int m = l[id] + r[id] >> 1;
                if (i ^ m && l[id] <= r[id]) v[m].push_back(id);
            }
            v[i].clear();
        }
        if (itr < lg - 1)
            for (int i = 0; i < n; i++) fen.fenw[i] = {0, 0};
    }
    for (int i = 0; i < q; i++) {
        auto [s, t, x, y] = qr[i];
        ans[i] = fen.qry(in[s]).second + fen.qry(in[t]).second - (fen.qry(in[lca(s, t)]).second << 1) - ans[i];
        cout << max(x - ans[i], -1) << '\n';
    }
}

Compilation message

currencies.cpp: In function 'int main()':
currencies.cpp:87:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   87 |                 int m = l[id] + r[id] >> 1;
currencies.cpp:50:18: warning: unused variable 'c' [-Wunused-variable]
   50 |     int n, m, q, c = 0;
      |                  ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 5 ms 832 KB Output is correct
6 Correct 6 ms 976 KB Output is correct
7 Correct 5 ms 832 KB Output is correct
8 Correct 7 ms 964 KB Output is correct
9 Correct 6 ms 980 KB Output is correct
10 Correct 7 ms 980 KB Output is correct
11 Correct 6 ms 992 KB Output is correct
12 Correct 6 ms 980 KB Output is correct
13 Correct 6 ms 976 KB Output is correct
14 Correct 7 ms 1064 KB Output is correct
15 Correct 7 ms 980 KB Output is correct
16 Correct 7 ms 1024 KB Output is correct
17 Correct 7 ms 980 KB Output is correct
18 Correct 7 ms 940 KB Output is correct
19 Correct 5 ms 976 KB Output is correct
20 Correct 5 ms 980 KB Output is correct
21 Correct 8 ms 1012 KB Output is correct
22 Correct 5 ms 980 KB Output is correct
23 Correct 6 ms 980 KB Output is correct
24 Correct 6 ms 1068 KB Output is correct
25 Correct 6 ms 1004 KB Output is correct
26 Correct 5 ms 968 KB Output is correct
27 Correct 4 ms 980 KB Output is correct
28 Correct 5 ms 980 KB Output is correct
29 Correct 5 ms 852 KB Output is correct
30 Correct 6 ms 952 KB Output is correct
31 Correct 6 ms 980 KB Output is correct
32 Correct 6 ms 1004 KB Output is correct
33 Correct 6 ms 980 KB Output is correct
34 Correct 6 ms 1072 KB Output is correct
35 Correct 6 ms 980 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 7 ms 964 KB Output is correct
3 Correct 6 ms 924 KB Output is correct
4 Correct 6 ms 980 KB Output is correct
5 Correct 537 ms 27184 KB Output is correct
6 Correct 632 ms 26252 KB Output is correct
7 Correct 614 ms 27180 KB Output is correct
8 Correct 512 ms 24640 KB Output is correct
9 Correct 454 ms 24016 KB Output is correct
10 Correct 851 ms 32956 KB Output is correct
11 Correct 838 ms 33124 KB Output is correct
12 Correct 856 ms 32756 KB Output is correct
13 Correct 858 ms 32860 KB Output is correct
14 Correct 820 ms 32964 KB Output is correct
15 Correct 926 ms 37472 KB Output is correct
16 Correct 813 ms 37832 KB Output is correct
17 Correct 985 ms 37160 KB Output is correct
18 Correct 1100 ms 33128 KB Output is correct
19 Correct 999 ms 33136 KB Output is correct
20 Correct 1089 ms 33024 KB Output is correct
21 Correct 699 ms 33648 KB Output is correct
22 Correct 758 ms 33604 KB Output is correct
23 Correct 865 ms 33700 KB Output is correct
24 Correct 820 ms 33800 KB Output is correct
25 Correct 831 ms 32872 KB Output is correct
26 Correct 862 ms 32692 KB Output is correct
27 Correct 720 ms 32764 KB Output is correct
28 Correct 385 ms 31484 KB Output is correct
29 Correct 362 ms 30732 KB Output is correct
30 Correct 524 ms 31384 KB Output is correct
31 Correct 497 ms 31076 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 6 ms 1108 KB Output is correct
3 Correct 7 ms 968 KB Output is correct
4 Correct 6 ms 980 KB Output is correct
5 Correct 725 ms 30844 KB Output is correct
6 Correct 680 ms 29984 KB Output is correct
7 Correct 677 ms 26416 KB Output is correct
8 Correct 1429 ms 38000 KB Output is correct
9 Correct 1297 ms 37960 KB Output is correct
10 Correct 1201 ms 38020 KB Output is correct
11 Correct 720 ms 37936 KB Output is correct
12 Correct 632 ms 37996 KB Output is correct
13 Correct 674 ms 37992 KB Output is correct
14 Correct 319 ms 37356 KB Output is correct
15 Correct 327 ms 36900 KB Output is correct
16 Correct 481 ms 37636 KB Output is correct
17 Correct 456 ms 37472 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 5 ms 832 KB Output is correct
6 Correct 6 ms 976 KB Output is correct
7 Correct 5 ms 832 KB Output is correct
8 Correct 7 ms 964 KB Output is correct
9 Correct 6 ms 980 KB Output is correct
10 Correct 7 ms 980 KB Output is correct
11 Correct 6 ms 992 KB Output is correct
12 Correct 6 ms 980 KB Output is correct
13 Correct 6 ms 976 KB Output is correct
14 Correct 7 ms 1064 KB Output is correct
15 Correct 7 ms 980 KB Output is correct
16 Correct 7 ms 1024 KB Output is correct
17 Correct 7 ms 980 KB Output is correct
18 Correct 7 ms 940 KB Output is correct
19 Correct 5 ms 976 KB Output is correct
20 Correct 5 ms 980 KB Output is correct
21 Correct 8 ms 1012 KB Output is correct
22 Correct 5 ms 980 KB Output is correct
23 Correct 6 ms 980 KB Output is correct
24 Correct 6 ms 1068 KB Output is correct
25 Correct 6 ms 1004 KB Output is correct
26 Correct 5 ms 968 KB Output is correct
27 Correct 4 ms 980 KB Output is correct
28 Correct 5 ms 980 KB Output is correct
29 Correct 5 ms 852 KB Output is correct
30 Correct 6 ms 952 KB Output is correct
31 Correct 6 ms 980 KB Output is correct
32 Correct 6 ms 1004 KB Output is correct
33 Correct 6 ms 980 KB Output is correct
34 Correct 6 ms 1072 KB Output is correct
35 Correct 6 ms 980 KB Output is correct
36 Correct 0 ms 212 KB Output is correct
37 Correct 7 ms 964 KB Output is correct
38 Correct 6 ms 924 KB Output is correct
39 Correct 6 ms 980 KB Output is correct
40 Correct 537 ms 27184 KB Output is correct
41 Correct 632 ms 26252 KB Output is correct
42 Correct 614 ms 27180 KB Output is correct
43 Correct 512 ms 24640 KB Output is correct
44 Correct 454 ms 24016 KB Output is correct
45 Correct 851 ms 32956 KB Output is correct
46 Correct 838 ms 33124 KB Output is correct
47 Correct 856 ms 32756 KB Output is correct
48 Correct 858 ms 32860 KB Output is correct
49 Correct 820 ms 32964 KB Output is correct
50 Correct 926 ms 37472 KB Output is correct
51 Correct 813 ms 37832 KB Output is correct
52 Correct 985 ms 37160 KB Output is correct
53 Correct 1100 ms 33128 KB Output is correct
54 Correct 999 ms 33136 KB Output is correct
55 Correct 1089 ms 33024 KB Output is correct
56 Correct 699 ms 33648 KB Output is correct
57 Correct 758 ms 33604 KB Output is correct
58 Correct 865 ms 33700 KB Output is correct
59 Correct 820 ms 33800 KB Output is correct
60 Correct 831 ms 32872 KB Output is correct
61 Correct 862 ms 32692 KB Output is correct
62 Correct 720 ms 32764 KB Output is correct
63 Correct 385 ms 31484 KB Output is correct
64 Correct 362 ms 30732 KB Output is correct
65 Correct 524 ms 31384 KB Output is correct
66 Correct 497 ms 31076 KB Output is correct
67 Correct 0 ms 212 KB Output is correct
68 Correct 6 ms 1108 KB Output is correct
69 Correct 7 ms 968 KB Output is correct
70 Correct 6 ms 980 KB Output is correct
71 Correct 725 ms 30844 KB Output is correct
72 Correct 680 ms 29984 KB Output is correct
73 Correct 677 ms 26416 KB Output is correct
74 Correct 1429 ms 38000 KB Output is correct
75 Correct 1297 ms 37960 KB Output is correct
76 Correct 1201 ms 38020 KB Output is correct
77 Correct 720 ms 37936 KB Output is correct
78 Correct 632 ms 37996 KB Output is correct
79 Correct 674 ms 37992 KB Output is correct
80 Correct 319 ms 37356 KB Output is correct
81 Correct 327 ms 36900 KB Output is correct
82 Correct 481 ms 37636 KB Output is correct
83 Correct 456 ms 37472 KB Output is correct
84 Correct 638 ms 25356 KB Output is correct
85 Correct 474 ms 21944 KB Output is correct
86 Correct 454 ms 20800 KB Output is correct
87 Correct 957 ms 33056 KB Output is correct
88 Correct 1038 ms 33024 KB Output is correct
89 Correct 1127 ms 33072 KB Output is correct
90 Correct 1060 ms 33304 KB Output is correct
91 Correct 1064 ms 33124 KB Output is correct
92 Correct 1250 ms 36148 KB Output is correct
93 Correct 1110 ms 37144 KB Output is correct
94 Correct 1324 ms 33276 KB Output is correct
95 Correct 1310 ms 33240 KB Output is correct
96 Correct 1380 ms 33168 KB Output is correct
97 Correct 1219 ms 33140 KB Output is correct
98 Correct 890 ms 33576 KB Output is correct
99 Correct 779 ms 33476 KB Output is correct
100 Correct 858 ms 33600 KB Output is correct
101 Correct 912 ms 33948 KB Output is correct
102 Correct 756 ms 33424 KB Output is correct
103 Correct 822 ms 33312 KB Output is correct
104 Correct 782 ms 33364 KB Output is correct
105 Correct 443 ms 30780 KB Output is correct
106 Correct 391 ms 31132 KB Output is correct
107 Correct 539 ms 30904 KB Output is correct
108 Correct 529 ms 31200 KB Output is correct