oj.uz

Submission #861898

# Submission time Handle Problem Language Result Execution time Memory
861898 2023-10-17T07:12:16 Z sleepntsheep Two Currencies (JOI23_currencies) C++17
100 / 100
 583 ms 127488 KB 
#include <cstdio>
#include <cstring>
#include <cassert>
#include <string>
#include <deque>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
#include <iostream>
#include <utility>
using namespace std;
using ll = long long;
using ld = long double;
#define ShinLena cin.tie(nullptr)->sync_with_stdio(false)

#define N 100005
#define ALL(x) x.begin(), x.end()

struct persist
{
    int a; ll b;
    persist *l, *r;
    persist(int a0, ll b0) : a(a0), b(b0), l(nullptr), r(nullptr) {}
    persist(persist *l0, persist *r0) : a((l0?l0->a:0) + (r0?r0->a:0)), b((l0?l0->b:0) + (r0?r0->b:0)), l(l0), r(r0) {}
    ~persist() {if (l) delete l; if (r) delete r;}
};

persist *build(int l, int r)
{
    if (l == r) return new persist(0, 0);
    return new persist(build(l, (l+r)/2), build((l+r)/2+1, r));
}

persist *upd(persist *v, int l, int r, ll w, int W)
{
    if (l == r) return new persist(v->a + 1, v->b + w);
    if (W <= (l+r)/2) return new persist(upd(v->l, l, (l+r)/2, w, W), v->r);
    return new persist(v->l, upd(v->r, (l+r)/2+1, r, w, W));
}

vector<ll> silver_cord;

ll qry(persist *u, persist *v, persist *a, int l, int r, ll k)
{
    if (l == r)
        return min(k, u->b + v->b - 2*a->b) / silver_cord[l];
    ll left = u->l->b + v->l->b - a->l->b * 2;
    if (k < left) return qry(u->l, v->l, a->l, l, (l+r)/2, k);
    return (u->l->a + v->l->a - a->l->a * 2) + qry(u->r, v->r, a->r, (l+r)/2+1, r, k - left);
}

ll qry_count(persist *u, persist *v, persist *a)
{
    return 1ll * u->a + v->a - a->a * 2ll;
}

int n, m, q, P[18][N], dep[N], ne;
vector<int> mark[N];
vector<pair<int, int>> g[N];
persist *root[N];

int lca(int u, int v)
{
    if (dep[u] < dep[v]) swap(v, u);
    int dt = dep[u] - dep[v];
    for (int j = 18; j--;) if (dt & (1 << j)) u = P[j][u];
    if (u == v) return u;
    for (int j = 18; j--;) if (P[j][u] != P[j][v]) u = P[j][u], v = P[j][v];
    return P[0][u];
}

void dfs(int u, int p, int d)
{
    dep[u] = d; P[0][u] = p; for (int j = 1; j < 18; ++j) P[j][u] = P[j-1][P[j-1][u]];
    for (auto [v, i] : g[u]) 
    {
        if (v == p) continue;
        root[v] = root[u];
        for (auto w : mark[i]) root[v] = upd(root[v], 0, ne, w, lower_bound(ALL(silver_cord), w) - silver_cord.begin());
        dfs(v, u, d+1);
    }
}

int main()
{
    ShinLena;
    cin >> n >> m >> q;
    for (int u, v, i = 1; i < n; ++i) cin >> u >> v, g[u].emplace_back(v, i), g[v].emplace_back(u, i);
    for (int p, c; m--; ) cin >> p >> c, mark[p].push_back(c), silver_cord.push_back(c);

    sort(ALL(silver_cord)); silver_cord.erase(unique(ALL(silver_cord)), silver_cord.end()); ne = silver_cord.size() - 1;

    root[1] = build(0, ne); dfs(1, 1, 1);

    for (ll s, t, gold, silver; q--; )
    {
        cin >> s >> t >> gold >> silver;
        persist *ps = root[s], *pt = root[t], *pa = root[lca(s, t)];
        int gone = qry(ps, pt, pa, 0, ne, silver), all = qry_count(ps, pt, pa);

        cout << ((all - gone > gold) ? -1 : gold - (all - gone)) << '\n';
    }

    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 2 ms 12764 KB Output is correct
3 Correct 2 ms 12632 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Correct 5 ms 14180 KB Output is correct
6 Correct 5 ms 14168 KB Output is correct
7 Correct 5 ms 13660 KB Output is correct
8 Correct 7 ms 14560 KB Output is correct
9 Correct 7 ms 14172 KB Output is correct
10 Correct 6 ms 14172 KB Output is correct
11 Correct 6 ms 14172 KB Output is correct
12 Correct 6 ms 14256 KB Output is correct
13 Correct 6 ms 14428 KB Output is correct
14 Correct 6 ms 14428 KB Output is correct
15 Correct 6 ms 12380 KB Output is correct
16 Correct 5 ms 14168 KB Output is correct
17 Correct 7 ms 14172 KB Output is correct
18 Correct 5 ms 12380 KB Output is correct
19 Correct 5 ms 14172 KB Output is correct
20 Correct 5 ms 14172 KB Output is correct
21 Correct 5 ms 14172 KB Output is correct
22 Correct 5 ms 14172 KB Output is correct
23 Correct 8 ms 14168 KB Output is correct
24 Correct 5 ms 14172 KB Output is correct
25 Correct 5 ms 14172 KB Output is correct
26 Correct 5 ms 10332 KB Output is correct
27 Correct 4 ms 8284 KB Output is correct
28 Correct 5 ms 14172 KB Output is correct
29 Correct 6 ms 14308 KB Output is correct
30 Correct 4 ms 12892 KB Output is correct
31 Correct 4 ms 12892 KB Output is correct
32 Correct 4 ms 12888 KB Output is correct
33 Correct 7 ms 14428 KB Output is correct
34 Correct 6 ms 14428 KB Output is correct
35 Correct 7 ms 14424 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 5 ms 12944 KB Output is correct
3 Correct 4 ms 12892 KB Output is correct
4 Correct 4 ms 12892 KB Output is correct
5 Correct 131 ms 27980 KB Output is correct
6 Correct 137 ms 26304 KB Output is correct
7 Correct 132 ms 26052 KB Output is correct
8 Correct 120 ms 25108 KB Output is correct
9 Correct 106 ms 25544 KB Output is correct
10 Correct 190 ms 29364 KB Output is correct
11 Correct 157 ms 29376 KB Output is correct
12 Correct 154 ms 29384 KB Output is correct
13 Correct 178 ms 29288 KB Output is correct
14 Correct 176 ms 29532 KB Output is correct
15 Correct 145 ms 38336 KB Output is correct
16 Correct 192 ms 39368 KB Output is correct
17 Correct 237 ms 38340 KB Output is correct
18 Correct 149 ms 29896 KB Output is correct
19 Correct 217 ms 30148 KB Output is correct
20 Correct 166 ms 30196 KB Output is correct
21 Correct 101 ms 29352 KB Output is correct
22 Correct 99 ms 29668 KB Output is correct
23 Correct 111 ms 29636 KB Output is correct
24 Correct 127 ms 29660 KB Output is correct
25 Correct 129 ms 29848 KB Output is correct
26 Correct 118 ms 29768 KB Output is correct
27 Correct 153 ms 29632 KB Output is correct
28 Correct 134 ms 29824 KB Output is correct
29 Correct 150 ms 29636 KB Output is correct
30 Correct 128 ms 29860 KB Output is correct
31 Correct 128 ms 29964 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12632 KB Output is correct
2 Correct 6 ms 14424 KB Output is correct
3 Correct 6 ms 14428 KB Output is correct
4 Correct 6 ms 14428 KB Output is correct
5 Correct 306 ms 89288 KB Output is correct
6 Correct 287 ms 76228 KB Output is correct
7 Correct 416 ms 112832 KB Output is correct
8 Correct 560 ms 127104 KB Output is correct
9 Correct 582 ms 127308 KB Output is correct
10 Correct 564 ms 127488 KB Output is correct
11 Correct 431 ms 126664 KB Output is correct
12 Correct 432 ms 126752 KB Output is correct
13 Correct 429 ms 126664 KB Output is correct
14 Correct 292 ms 127428 KB Output is correct
15 Correct 274 ms 127128 KB Output is correct
16 Correct 335 ms 127444 KB Output is correct
17 Correct 322 ms 127100 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 2 ms 12764 KB Output is correct
3 Correct 2 ms 12632 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Correct 5 ms 14180 KB Output is correct
6 Correct 5 ms 14168 KB Output is correct
7 Correct 5 ms 13660 KB Output is correct
8 Correct 7 ms 14560 KB Output is correct
9 Correct 7 ms 14172 KB Output is correct
10 Correct 6 ms 14172 KB Output is correct
11 Correct 6 ms 14172 KB Output is correct
12 Correct 6 ms 14256 KB Output is correct
13 Correct 6 ms 14428 KB Output is correct
14 Correct 6 ms 14428 KB Output is correct
15 Correct 6 ms 12380 KB Output is correct
16 Correct 5 ms 14168 KB Output is correct
17 Correct 7 ms 14172 KB Output is correct
18 Correct 5 ms 12380 KB Output is correct
19 Correct 5 ms 14172 KB Output is correct
20 Correct 5 ms 14172 KB Output is correct
21 Correct 5 ms 14172 KB Output is correct
22 Correct 5 ms 14172 KB Output is correct
23 Correct 8 ms 14168 KB Output is correct
24 Correct 5 ms 14172 KB Output is correct
25 Correct 5 ms 14172 KB Output is correct
26 Correct 5 ms 10332 KB Output is correct
27 Correct 4 ms 8284 KB Output is correct
28 Correct 5 ms 14172 KB Output is correct
29 Correct 6 ms 14308 KB Output is correct
30 Correct 4 ms 12892 KB Output is correct
31 Correct 4 ms 12892 KB Output is correct
32 Correct 4 ms 12888 KB Output is correct
33 Correct 7 ms 14428 KB Output is correct
34 Correct 6 ms 14428 KB Output is correct
35 Correct 7 ms 14424 KB Output is correct
36 Correct 2 ms 12636 KB Output is correct
37 Correct 5 ms 12944 KB Output is correct
38 Correct 4 ms 12892 KB Output is correct
39 Correct 4 ms 12892 KB Output is correct
40 Correct 131 ms 27980 KB Output is correct
41 Correct 137 ms 26304 KB Output is correct
42 Correct 132 ms 26052 KB Output is correct
43 Correct 120 ms 25108 KB Output is correct
44 Correct 106 ms 25544 KB Output is correct
45 Correct 190 ms 29364 KB Output is correct
46 Correct 157 ms 29376 KB Output is correct
47 Correct 154 ms 29384 KB Output is correct
48 Correct 178 ms 29288 KB Output is correct
49 Correct 176 ms 29532 KB Output is correct
50 Correct 145 ms 38336 KB Output is correct
51 Correct 192 ms 39368 KB Output is correct
52 Correct 237 ms 38340 KB Output is correct
53 Correct 149 ms 29896 KB Output is correct
54 Correct 217 ms 30148 KB Output is correct
55 Correct 166 ms 30196 KB Output is correct
56 Correct 101 ms 29352 KB Output is correct
57 Correct 99 ms 29668 KB Output is correct
58 Correct 111 ms 29636 KB Output is correct
59 Correct 127 ms 29660 KB Output is correct
60 Correct 129 ms 29848 KB Output is correct
61 Correct 118 ms 29768 KB Output is correct
62 Correct 153 ms 29632 KB Output is correct
63 Correct 134 ms 29824 KB Output is correct
64 Correct 150 ms 29636 KB Output is correct
65 Correct 128 ms 29860 KB Output is correct
66 Correct 128 ms 29964 KB Output is correct
67 Correct 2 ms 12632 KB Output is correct
68 Correct 6 ms 14424 KB Output is correct
69 Correct 6 ms 14428 KB Output is correct
70 Correct 6 ms 14428 KB Output is correct
71 Correct 306 ms 89288 KB Output is correct
72 Correct 287 ms 76228 KB Output is correct
73 Correct 416 ms 112832 KB Output is correct
74 Correct 560 ms 127104 KB Output is correct
75 Correct 582 ms 127308 KB Output is correct
76 Correct 564 ms 127488 KB Output is correct
77 Correct 431 ms 126664 KB Output is correct
78 Correct 432 ms 126752 KB Output is correct
79 Correct 429 ms 126664 KB Output is correct
80 Correct 292 ms 127428 KB Output is correct
81 Correct 274 ms 127128 KB Output is correct
82 Correct 335 ms 127444 KB Output is correct
83 Correct 322 ms 127100 KB Output is correct
84 Correct 293 ms 109528 KB Output is correct
85 Correct 240 ms 99016 KB Output is correct
86 Correct 191 ms 72836 KB Output is correct
87 Correct 352 ms 117696 KB Output is correct
88 Correct 356 ms 117704 KB Output is correct
89 Correct 351 ms 117732 KB Output is correct
90 Correct 371 ms 117628 KB Output is correct
91 Correct 347 ms 117564 KB Output is correct
92 Correct 578 ms 123848 KB Output is correct
93 Correct 583 ms 125756 KB Output is correct
94 Correct 467 ms 117700 KB Output is correct
95 Correct 469 ms 117732 KB Output is correct
96 Correct 476 ms 117696 KB Output is correct
97 Correct 530 ms 117708 KB Output is correct
98 Correct 336 ms 117148 KB Output is correct
99 Correct 342 ms 116944 KB Output is correct
100 Correct 366 ms 117440 KB Output is correct
101 Correct 361 ms 117248 KB Output is correct
102 Correct 408 ms 117560 KB Output is correct
103 Correct 409 ms 117492 KB Output is correct
104 Correct 419 ms 117368 KB Output is correct
105 Correct 290 ms 117592 KB Output is correct
106 Correct 273 ms 117736 KB Output is correct
107 Correct 290 ms 117464 KB Output is correct
108 Correct 282 ms 117328 KB Output is correct