oj.uz

Submission #958267

# Submission time Handle Problem Language Result Execution time Memory
958267 2024-04-05T09:12:49 Z Szil Two Currencies (JOI23_currencies) C++14
28 / 100
 327 ms 122816 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int MAXN = 100'001;
const int MAXK = 20;

struct Node {
    Node *l, *r;
    ll sum = 0;
    int cnt = 0;

    Node(ll x, int y) : sum(x), cnt(y), l(nullptr), r(nullptr) {}
    Node(Node *a, Node *b) : l(a), r(b) {
        if (a) {
            sum += a->sum;
            cnt += a->cnt;
        }
        if (b) {
            sum += b->sum;
            cnt += b->cnt;
        }
    }
};

Node *build(int tl, int tr) {
    if (tl == tr) {
        return new Node(0, 0);
    } else {
        int tm = (tl + tr) / 2;
        return new Node(build(tl, tm), build(tm+1, tr));
    }
}

Node *upd(Node *v, int tl, int tr, int pos, ll val, ll cnt) {
    if (tl == tr) {
        return new Node(v->sum + val, v->cnt + cnt);
    } else {
        int tm = (tl + tr) / 2;
        if (pos <= tm) {
            return new Node(upd(v->l, tl, tm, pos, val, cnt), v->r);
        } else {
            return new Node(v->l, upd(v->r, tm+1, tr, pos, val, cnt));
        }
    }
}

ll qry(Node *u, Node *v, Node *lca, int tl, int tr, ll silver) {
    if (tl == tr) {
        ll val = u->sum + v->sum - 2 * lca->sum;
        ll golds = u->cnt + v->cnt  - 2 * lca->cnt;
        ll base = golds ? val / golds : 0;
        ll bought = base ? silver / base : 0;
        return max(0ll, golds - bought);
    } else {
        int tm = (tl + tr) / 2;
        ll val = u->l->sum + v->l->sum - 2 * lca->l->sum;
        if (val <= silver) {
            return qry(u->r, v->r, lca->r, tm+1, tr, silver - val);
        } else {
            ll golds = u->r->cnt + v->r->cnt - 2 * lca->r->cnt;
            return golds + qry(u->l, v->l, lca->l, tl, tm, silver);
        }
    }
}

vector<int> g[MAXN];
int up[MAXN][MAXK], tin[MAXN], tout[MAXN], n, m, q, timer = 1;
Node *root[MAXN];
vector<ll> checkpoints[MAXN];

void dfs(int u, int p = -1) {
    tin[u] = timer++;
    for (int v : g[u]) {
        if (v != p) {
            up[v][0] = u;
            dfs(v, u);
        }
    }
    tout[u] = timer++;
}

bool is_ancestor(int u, int v) {
    return tin[u] <= tin[v] && tout[v] <= tout[u];
}

int lca(int u, int v) {
    if (is_ancestor(u, v)) return u;
    if (is_ancestor(v, u)) return v;
    for (int k = MAXK-1; k >= 0; k--) {
        if (up[u][k] && !is_ancestor(up[u][k], v)) {
            u = up[u][k];
        }
    }
    return up[u][0];
}

void prelift() {
    dfs(1);
    for (int k = 1; k < MAXK; k++) {
        for (int i = 1; i <= n; i++) {
            up[i][k] = up[up[i][k-1]][k-1];
        }
    }
}

void dfs2(const vector<int> &comp, int u, int p = -1) {

    if (p == -1) {
        root[u] = build(1, n);
    } else {
        root[u] = root[up[u][0]];
        for (ll c : checkpoints[u]) {
            int pos = lower_bound(comp.begin(), comp.end(), c)-comp.begin();
            root[u] = upd(root[u], 1, n, pos, c, 1);
        }
    }

    for (int v : g[u]) {
        if (v != p) dfs2(comp, v, u);
    }
}

vector<int> comp = {0};
void build_tree() {
    sort(comp.begin(), comp.end());
    comp.erase(unique(comp.begin(), comp.end()), comp.end());
    g[0].emplace_back(1);
    dfs2(comp, 0);
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m >> q;
    vector<pair<int, int>> edges;
    for (int i = 1; i <= n-1; i++) {
        int u, v; cin >> u >> v;
        edges.emplace_back(u, v);
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }

    prelift();

    for (int i = 1; i <= m; i++) {
        ll p, c; cin >> p >> c;
        auto [u, v] = edges[p-1];
        if (tin[u] > tin[v]) swap(u, v);
        comp.emplace_back(c);
        checkpoints[v].emplace_back(c);
    }

    build_tree();

    while (q--) {
        ll s, t, x, y; cin >> s >> t >> x >> y;
        int v = lca(s, t);
        cout << max(-1ll, x-qry(root[s], root[t], root[v], 1, n, y)) << "\n";
    }
    return 0;
}

Compilation message

currencies.cpp: In constructor 'Node::Node(ll, int)':
currencies.cpp:12:9: warning: 'Node::cnt' will be initialized after [-Wreorder]
   12 |     int cnt = 0;
      |         ^~~
currencies.cpp:10:11: warning:   'Node* Node::l' [-Wreorder]
   10 |     Node *l, *r;
      |           ^
currencies.cpp:14:5: warning:   when initialized here [-Wreorder]
   14 |     Node(ll x, int y) : sum(x), cnt(y), l(nullptr), r(nullptr) {}
      |     ^~~~
currencies.cpp: In function 'int main()':
currencies.cpp:148:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  148 |         auto [u, v] = edges[p-1];
      |              ^

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8284 KB Output is correct
2 Correct 2 ms 8284 KB Output is correct
3 Correct 2 ms 8284 KB Output is correct
4 Correct 3 ms 8304 KB Output is correct
5 Correct 5 ms 9564 KB Output is correct
6 Correct 7 ms 9824 KB Output is correct
7 Incorrect 6 ms 9308 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8284 KB Output is correct
2 Correct 5 ms 9820 KB Output is correct
3 Correct 4 ms 9844 KB Output is correct
4 Correct 5 ms 9816 KB Output is correct
5 Correct 194 ms 106416 KB Output is correct
6 Correct 202 ms 95496 KB Output is correct
7 Correct 185 ms 83220 KB Output is correct
8 Correct 162 ms 80832 KB Output is correct
9 Correct 206 ms 85828 KB Output is correct
10 Correct 259 ms 115080 KB Output is correct
11 Correct 259 ms 115140 KB Output is correct
12 Correct 259 ms 115268 KB Output is correct
13 Correct 298 ms 115144 KB Output is correct
14 Correct 264 ms 115100 KB Output is correct
15 Correct 276 ms 122304 KB Output is correct
16 Correct 264 ms 122816 KB Output is correct
17 Correct 286 ms 122112 KB Output is correct
18 Correct 292 ms 115464 KB Output is correct
19 Correct 327 ms 115192 KB Output is correct
20 Correct 293 ms 115392 KB Output is correct
21 Correct 221 ms 115588 KB Output is correct
22 Correct 229 ms 115472 KB Output is correct
23 Correct 214 ms 115516 KB Output is correct
24 Correct 222 ms 115448 KB Output is correct
25 Correct 217 ms 114932 KB Output is correct
26 Correct 242 ms 115188 KB Output is correct
27 Correct 220 ms 114920 KB Output is correct
28 Correct 211 ms 115172 KB Output is correct
29 Correct 200 ms 115340 KB Output is correct
30 Correct 197 ms 115140 KB Output is correct
31 Correct 206 ms 115280 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8280 KB Output is correct
2 Correct 6 ms 9820 KB Output is correct
3 Correct 5 ms 10076 KB Output is correct
4 Correct 5 ms 10076 KB Output is correct
5 Correct 260 ms 94752 KB Output is correct
6 Correct 237 ms 82372 KB Output is correct
7 Incorrect 293 ms 102956 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8284 KB Output is correct
2 Correct 2 ms 8284 KB Output is correct
3 Correct 2 ms 8284 KB Output is correct
4 Correct 3 ms 8304 KB Output is correct
5 Correct 5 ms 9564 KB Output is correct
6 Correct 7 ms 9824 KB Output is correct
7 Incorrect 6 ms 9308 KB Output isn't correct
8 Halted 0 ms 0 KB -