oj.uz

Submission #861903

# Submission time Handle Problem Language Result Execution time Memory
861903 2023-10-17T07:16:11 Z sleepntsheep Two Currencies (JOI23_currencies) C++17
100 / 100
 566 ms 126432 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));
}

int cord[N], ne;

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) / 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);
}

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

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

inline int lca(int u, int v)
{
    if (dep[u] < dep[v]) swap(v, u);
    int dt = dep[u] - dep[v];
    for (int j = 17; j--;) if (dt & (1 << j)) u = P[j][u];
    if (u == v) return u;
    for (int j = 17; 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 < 17; ++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(cord, cord+ne, w) - cord);
        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), cord[ne++] = c;

    sort(cord, cord+ne), ne = unique(cord, cord+ne) - cord - 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 12768 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Correct 4 ms 14172 KB Output is correct
6 Correct 5 ms 14172 KB Output is correct
7 Correct 4 ms 13660 KB Output is correct
8 Correct 6 ms 14172 KB Output is correct
9 Correct 5 ms 14172 KB Output is correct
10 Correct 5 ms 14172 KB Output is correct
11 Correct 6 ms 14172 KB Output is correct
12 Correct 5 ms 14424 KB Output is correct
13 Correct 5 ms 14264 KB Output is correct
14 Correct 5 ms 14428 KB Output is correct
15 Correct 5 ms 14224 KB Output is correct
16 Correct 5 ms 14172 KB Output is correct
17 Correct 6 ms 14356 KB Output is correct
18 Correct 6 ms 14172 KB Output is correct
19 Correct 5 ms 14172 KB Output is correct
20 Correct 6 ms 14204 KB Output is correct
21 Correct 5 ms 14172 KB Output is correct
22 Correct 5 ms 14324 KB Output is correct
23 Correct 5 ms 14172 KB Output is correct
24 Correct 5 ms 14172 KB Output is correct
25 Correct 6 ms 14168 KB Output is correct
26 Correct 5 ms 14172 KB Output is correct
27 Correct 5 ms 14172 KB Output is correct
28 Correct 5 ms 14172 KB Output is correct
29 Correct 5 ms 14188 KB Output is correct
30 Correct 4 ms 13104 KB Output is correct
31 Correct 4 ms 12892 KB Output is correct
32 Correct 3 ms 12892 KB Output is correct
33 Correct 5 ms 14500 KB Output is correct
34 Correct 5 ms 14456 KB Output is correct
35 Correct 5 ms 14428 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12740 KB Output is correct
2 Correct 3 ms 12892 KB Output is correct
3 Correct 4 ms 12892 KB Output is correct
4 Correct 4 ms 12976 KB Output is correct
5 Correct 112 ms 26308 KB Output is correct
6 Correct 91 ms 24540 KB Output is correct
7 Correct 92 ms 23860 KB Output is correct
8 Correct 85 ms 23176 KB Output is correct
9 Correct 83 ms 23636 KB Output is correct
10 Correct 131 ms 26964 KB Output is correct
11 Correct 115 ms 26960 KB Output is correct
12 Correct 128 ms 27208 KB Output is correct
13 Correct 117 ms 26904 KB Output is correct
14 Correct 118 ms 27044 KB Output is correct
15 Correct 139 ms 35360 KB Output is correct
16 Correct 153 ms 36160 KB Output is correct
17 Correct 139 ms 35152 KB Output is correct
18 Correct 133 ms 27004 KB Output is correct
19 Correct 133 ms 26964 KB Output is correct
20 Correct 131 ms 27016 KB Output is correct
21 Correct 97 ms 26568 KB Output is correct
22 Correct 98 ms 26824 KB Output is correct
23 Correct 97 ms 26820 KB Output is correct
24 Correct 98 ms 26984 KB Output is correct
25 Correct 111 ms 26832 KB Output is correct
26 Correct 111 ms 26708 KB Output is correct
27 Correct 108 ms 26828 KB Output is correct
28 Correct 109 ms 26960 KB Output is correct
29 Correct 104 ms 27016 KB Output is correct
30 Correct 127 ms 26964 KB Output is correct
31 Correct 138 ms 27220 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 5 ms 14428 KB Output is correct
3 Correct 5 ms 14300 KB Output is correct
4 Correct 5 ms 14428 KB Output is correct
5 Correct 269 ms 88916 KB Output is correct
6 Correct 252 ms 75704 KB Output is correct
7 Correct 357 ms 112208 KB Output is correct
8 Correct 469 ms 125620 KB Output is correct
9 Correct 481 ms 125780 KB Output is correct
10 Correct 470 ms 125264 KB Output is correct
11 Correct 413 ms 124804 KB Output is correct
12 Correct 421 ms 125252 KB Output is correct
13 Correct 427 ms 125496 KB Output is correct
14 Correct 288 ms 126108 KB Output is correct
15 Correct 278 ms 126432 KB Output is correct
16 Correct 320 ms 126032 KB Output is correct
17 Correct 319 ms 126328 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 12768 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Correct 4 ms 14172 KB Output is correct
6 Correct 5 ms 14172 KB Output is correct
7 Correct 4 ms 13660 KB Output is correct
8 Correct 6 ms 14172 KB Output is correct
9 Correct 5 ms 14172 KB Output is correct
10 Correct 5 ms 14172 KB Output is correct
11 Correct 6 ms 14172 KB Output is correct
12 Correct 5 ms 14424 KB Output is correct
13 Correct 5 ms 14264 KB Output is correct
14 Correct 5 ms 14428 KB Output is correct
15 Correct 5 ms 14224 KB Output is correct
16 Correct 5 ms 14172 KB Output is correct
17 Correct 6 ms 14356 KB Output is correct
18 Correct 6 ms 14172 KB Output is correct
19 Correct 5 ms 14172 KB Output is correct
20 Correct 6 ms 14204 KB Output is correct
21 Correct 5 ms 14172 KB Output is correct
22 Correct 5 ms 14324 KB Output is correct
23 Correct 5 ms 14172 KB Output is correct
24 Correct 5 ms 14172 KB Output is correct
25 Correct 6 ms 14168 KB Output is correct
26 Correct 5 ms 14172 KB Output is correct
27 Correct 5 ms 14172 KB Output is correct
28 Correct 5 ms 14172 KB Output is correct
29 Correct 5 ms 14188 KB Output is correct
30 Correct 4 ms 13104 KB Output is correct
31 Correct 4 ms 12892 KB Output is correct
32 Correct 3 ms 12892 KB Output is correct
33 Correct 5 ms 14500 KB Output is correct
34 Correct 5 ms 14456 KB Output is correct
35 Correct 5 ms 14428 KB Output is correct
36 Correct 2 ms 12740 KB Output is correct
37 Correct 3 ms 12892 KB Output is correct
38 Correct 4 ms 12892 KB Output is correct
39 Correct 4 ms 12976 KB Output is correct
40 Correct 112 ms 26308 KB Output is correct
41 Correct 91 ms 24540 KB Output is correct
42 Correct 92 ms 23860 KB Output is correct
43 Correct 85 ms 23176 KB Output is correct
44 Correct 83 ms 23636 KB Output is correct
45 Correct 131 ms 26964 KB Output is correct
46 Correct 115 ms 26960 KB Output is correct
47 Correct 128 ms 27208 KB Output is correct
48 Correct 117 ms 26904 KB Output is correct
49 Correct 118 ms 27044 KB Output is correct
50 Correct 139 ms 35360 KB Output is correct
51 Correct 153 ms 36160 KB Output is correct
52 Correct 139 ms 35152 KB Output is correct
53 Correct 133 ms 27004 KB Output is correct
54 Correct 133 ms 26964 KB Output is correct
55 Correct 131 ms 27016 KB Output is correct
56 Correct 97 ms 26568 KB Output is correct
57 Correct 98 ms 26824 KB Output is correct
58 Correct 97 ms 26820 KB Output is correct
59 Correct 98 ms 26984 KB Output is correct
60 Correct 111 ms 26832 KB Output is correct
61 Correct 111 ms 26708 KB Output is correct
62 Correct 108 ms 26828 KB Output is correct
63 Correct 109 ms 26960 KB Output is correct
64 Correct 104 ms 27016 KB Output is correct
65 Correct 127 ms 26964 KB Output is correct
66 Correct 138 ms 27220 KB Output is correct
67 Correct 2 ms 12636 KB Output is correct
68 Correct 5 ms 14428 KB Output is correct
69 Correct 5 ms 14300 KB Output is correct
70 Correct 5 ms 14428 KB Output is correct
71 Correct 269 ms 88916 KB Output is correct
72 Correct 252 ms 75704 KB Output is correct
73 Correct 357 ms 112208 KB Output is correct
74 Correct 469 ms 125620 KB Output is correct
75 Correct 481 ms 125780 KB Output is correct
76 Correct 470 ms 125264 KB Output is correct
77 Correct 413 ms 124804 KB Output is correct
78 Correct 421 ms 125252 KB Output is correct
79 Correct 427 ms 125496 KB Output is correct
80 Correct 288 ms 126108 KB Output is correct
81 Correct 278 ms 126432 KB Output is correct
82 Correct 320 ms 126032 KB Output is correct
83 Correct 319 ms 126328 KB Output is correct
84 Correct 264 ms 108360 KB Output is correct
85 Correct 242 ms 98516 KB Output is correct
86 Correct 184 ms 72016 KB Output is correct
87 Correct 344 ms 116564 KB Output is correct
88 Correct 350 ms 116688 KB Output is correct
89 Correct 341 ms 116564 KB Output is correct
90 Correct 354 ms 116696 KB Output is correct
91 Correct 337 ms 116668 KB Output is correct
92 Correct 566 ms 122936 KB Output is correct
93 Correct 543 ms 124500 KB Output is correct
94 Correct 460 ms 116820 KB Output is correct
95 Correct 461 ms 117164 KB Output is correct
96 Correct 452 ms 116936 KB Output is correct
97 Correct 455 ms 116696 KB Output is correct
98 Correct 300 ms 115912 KB Output is correct
99 Correct 303 ms 115652 KB Output is correct
100 Correct 295 ms 115720 KB Output is correct
101 Correct 287 ms 115656 KB Output is correct
102 Correct 324 ms 116056 KB Output is correct
103 Correct 323 ms 115920 KB Output is correct
104 Correct 329 ms 115920 KB Output is correct
105 Correct 252 ms 116036 KB Output is correct
106 Correct 241 ms 116308 KB Output is correct
107 Correct 261 ms 116720 KB Output is correct
108 Correct 252 ms 116152 KB Output is correct