oj.uz

Submission #861894

# Submission time Handle Problem Language Result Execution time Memory
861894 2023-10-17T07:09:59 Z sleepntsheep Two Currencies (JOI23_currencies) C++17
28 / 100
 312 ms 128872 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)
    {
        if (l >= (int)silver_cord.size()) return 0;
        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];
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, n, 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());

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

    for (ll s, t, a, gold, silver; q--; )
    {
        cin >> s >> t >> gold >> silver;
        a = lca(s, t);
        persist *ps = root[s], *pt = root[t], *pa = root[a];
        int gone = qry(ps, pt, pa, 0, n, 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 12636 KB Output is correct
2 Correct 2 ms 12648 KB Output is correct
3 Correct 3 ms 12636 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Incorrect 5 ms 14204 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 6 ms 14100 KB Output is correct
3 Correct 5 ms 14424 KB Output is correct
4 Correct 5 ms 14152 KB Output is correct
5 Correct 223 ms 109480 KB Output is correct
6 Correct 272 ms 98756 KB Output is correct
7 Correct 196 ms 86596 KB Output is correct
8 Correct 178 ms 83540 KB Output is correct
9 Correct 169 ms 87880 KB Output is correct
10 Correct 250 ms 119336 KB Output is correct
11 Correct 255 ms 119236 KB Output is correct
12 Correct 247 ms 119232 KB Output is correct
13 Correct 248 ms 119248 KB Output is correct
14 Correct 256 ms 119232 KB Output is correct
15 Correct 268 ms 127940 KB Output is correct
16 Correct 275 ms 128872 KB Output is correct
17 Correct 277 ms 127524 KB Output is correct
18 Correct 278 ms 119348 KB Output is correct
19 Correct 288 ms 118980 KB Output is correct
20 Correct 262 ms 119244 KB Output is correct
21 Correct 207 ms 118536 KB Output is correct
22 Correct 202 ms 118720 KB Output is correct
23 Correct 204 ms 118728 KB Output is correct
24 Correct 208 ms 118872 KB Output is correct
25 Correct 216 ms 119068 KB Output is correct
26 Correct 216 ms 119112 KB Output is correct
27 Correct 214 ms 119208 KB Output is correct
28 Correct 180 ms 118912 KB Output is correct
29 Correct 180 ms 118980 KB Output is correct
30 Correct 195 ms 119240 KB Output is correct
31 Correct 188 ms 119236 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 Correct 5 ms 14448 KB Output is correct
3 Correct 5 ms 14428 KB Output is correct
4 Correct 5 ms 14428 KB Output is correct
5 Correct 298 ms 94532 KB Output is correct
6 Correct 258 ms 82352 KB Output is correct
7 Incorrect 312 ms 104348 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 2 ms 12648 KB Output is correct
3 Correct 3 ms 12636 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Incorrect 5 ms 14204 KB Output isn't correct
6 Halted 0 ms 0 KB -