oj.uz

Submission #861901

# Submission time Handle Problem Language Result Execution time Memory
861901 2023-10-17T07:15:23 Z sleepntsheep Two Currencies (JOI23_currencies) C++17
28 / 100
 154 ms 42104 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;

    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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12632 KB Output is correct
2 Correct 2 ms 12632 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Runtime error 15 ms 28312 KB Execution killed with signal 8
6 Halted 0 ms 0 KB -

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12632 KB Output is correct
2 Correct 4 ms 13148 KB Output is correct
3 Correct 4 ms 13148 KB Output is correct
4 Correct 4 ms 13148 KB Output is correct
5 Correct 127 ms 31296 KB Output is correct
6 Correct 101 ms 29268 KB Output is correct
7 Correct 104 ms 28032 KB Output is correct
8 Correct 89 ms 27296 KB Output is correct
9 Correct 97 ms 28012 KB Output is correct
10 Correct 127 ms 33084 KB Output is correct
11 Correct 128 ms 33228 KB Output is correct
12 Correct 129 ms 32980 KB Output is correct
13 Correct 150 ms 33100 KB Output is correct
14 Correct 127 ms 32932 KB Output is correct
15 Correct 148 ms 41444 KB Output is correct
16 Correct 154 ms 42104 KB Output is correct
17 Correct 149 ms 40992 KB Output is correct
18 Correct 138 ms 32852 KB Output is correct
19 Correct 152 ms 33000 KB Output is correct
20 Correct 144 ms 32852 KB Output is correct
21 Correct 105 ms 32708 KB Output is correct
22 Correct 106 ms 32520 KB Output is correct
23 Correct 120 ms 32820 KB Output is correct
24 Correct 105 ms 32528 KB Output is correct
25 Correct 118 ms 32712 KB Output is correct
26 Correct 120 ms 32716 KB Output is correct
27 Correct 116 ms 32872 KB Output is correct
28 Correct 113 ms 32852 KB Output is correct
29 Correct 114 ms 32588 KB Output is correct
30 Correct 115 ms 33104 KB Output is correct
31 Correct 118 ms 33108 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12632 KB Output is correct
2 Runtime error 15 ms 28852 KB Execution killed with signal 8
3 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12632 KB Output is correct
2 Correct 2 ms 12632 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Runtime error 15 ms 28312 KB Execution killed with signal 8
6 Halted 0 ms 0 KB -