oj.uz

Submission #907009

# Submission time Handle Problem Language Result Execution time Memory
907009 2024-01-15T05:50:58 Z CDuong Two Currencies (JOI23_currencies) C++17
100 / 100
 643 ms 94528 KB 
/*
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,fma,bmi,bmi2,sse4.2,popcnt,lzcnt")
*/

#include <bits/stdc++.h>
#define taskname ""
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define int long long
#define i64 long long
#define pb push_back
#define ff first
#define ss second
#define isz(x) (int)x.size()
using namespace std;

const int mxN = 1e5 + 5;
const int mod = 1e9 + 7;
const int LOG = 20;
const i64 oo = 1e18;

void adds(pair<i64, int> &val, pair<i64, int> nval) {
    val.ff += nval.ff;
    val.ss += nval.ss;
}

struct FenwickTree {
    int n;
    vector<pair<i64, int>> data;

    FenwickTree() {};
    FenwickTree(int n) : n(n), data(n + 10) {}

    void update(int idx, pair<i64, int> val) {
        while (idx <= n) {
            adds(data[idx], val);
            idx += idx & -idx;
        }
    }

    pair<i64, int> get(int idx) {
        pair<i64, int> res = {0, 0};
        while (idx) {
            adds(res, data[idx]);
            idx -= idx & -idx;
        }
        return res;
    }
} fenw;

struct Checkpoint {
    int p, c;
    Checkpoint(int p, int c) : p(p), c(c) {}
    bool operator < (const Checkpoint &cp) const {
        return c < cp.c;
    }
};

struct Query {
    int s, t, x, y;
    Query(int s, int t, int x, int y) : s(s), t(t), x(x), y(y) {}
};

int n, m, q, ans[mxN];
vector<Query> qq;
vector<Checkpoint> cp;
pair<int, int> edges[mxN];
vector<pair<int, int>> G[mxN];
int tin[mxN], tout[mxN], ap[mxN], par[mxN], dep[mxN], cnt_edges[mxN], h[mxN], tdfs, ecnt;
pair<int, int> euler[LOG][2 * mxN];
int ptr_pbs = -1;

void dfs(int v, int p) {
    tin[v] = ++tdfs;
    dep[v] = dep[p] + 1;
    par[v] = p;
    euler[0][++ecnt] = {dep[v], v};
    ap[v] = ecnt;
    for (auto [u, eidx] : G[v]) if (u != p) {
        h[u] = h[v] + cnt_edges[eidx];
        dfs(u, v);
        euler[0][++ecnt] = {dep[v], v};
    }
    tout[v] = tdfs;
}

void build_euler() {
    for (int i = 1, p = 1; (p << 1) <= ecnt; ++i, p <<= 1) {
        for (int j = 1; j + (p << 1) - 1 <= ecnt; ++j) {
            euler[i][j] = min(euler[i - 1][j], euler[i - 1][j + p]);
        }
    }
}

int LCA(int u, int v) {
    int l = ap[u], r = ap[v];
    if (l > r) swap(l, r);
    int len = r - l + 1, lg_len = 31 - __builtin_clz(len);
    return min(euler[lg_len][l], euler[lg_len][r - (1 << lg_len) + 1]).ss;
}

void add(int cpidx) {
    auto [p, c] = cp[cpidx];
    auto [u, v] = edges[p];
    if (dep[u] < dep[v]) swap(u, v);
    fenw.update(tin[u], {c, 1});
    fenw.update(tout[u] + 1, {-c, -1});
}

void del(int cpidx) {
    auto [p, c] = cp[cpidx];
    auto [u, v] = edges[p];
    if (dep[u] < dep[v]) swap(u, v);
    fenw.update(tin[u], {-c, -1});
    fenw.update(tout[u] + 1, {c, 1});
}

void pbs(int l, int r, vector<int> &qq_idx) {
    if (l > r or qq_idx.empty()) return;

    int mid = (l + r) >> 1;
    while (ptr_pbs < mid) add(++ptr_pbs);
    while (ptr_pbs > mid) del(ptr_pbs--);

    vector<int> qql, qqr;

    for (int idx : qq_idx) {
        auto [s, t, x, y] = qq[idx];
        int lca = LCA(s, t);

        pair<i64, int> total_silver = {0, 0};
        adds(total_silver, fenw.get(tin[s]));
        adds(total_silver, fenw.get(tin[t]));
        auto cur = fenw.get(tin[lca]); cur.ff *= -2, cur.ss *= -2;
        adds(total_silver, cur);

        if (total_silver.ff <= x) {
            ans[idx] = max(ans[idx], y - (h[s] + h[t] - 2 * h[lca] - total_silver.ss));
            qqr.emplace_back(idx);
        }
        else {
            qql.emplace_back(idx);
        }
    }

    pbs(l, mid - 1, qql);
    pbs(mid + 1, r, qqr);
}

void solve() {
    cin >> n >> m >> q;
    fenw = FenwickTree(n);
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        G[u].emplace_back(v, i);
        G[v].emplace_back(u, i);
        edges[i] = {u, v};
    }
    for (int i = 1; i <= m; ++i) {
        int p, c;
        cin >> p >> c;
        cp.emplace_back(p, c);
        cnt_edges[p]++;
    }
    sort(all(cp));
    for (int i = 1; i <= q; ++i) {
        int s, t, x, y;
        cin >> s >> t >> y >> x;
        qq.emplace_back(s, t, x, y);
        ans[i - 1] = -1;
    }
    dfs(1, 0);
    build_euler();
    vector<int> qq_idx(q); iota(all(qq_idx), 0);
    pbs(-1, m - 1, qq_idx);
    for (int i = 0; i < q; ++i)
        cout << ans[i] << "\n";
}

signed main() {

#ifndef CDuongg
    if(fopen(taskname".inp", "r"))
        assert(freopen(taskname".inp", "r", stdin)), assert(freopen(taskname".out", "w", stdout));
#else
    freopen("bai3.inp", "r", stdin);
    freopen("bai3.out", "w", stdout);
    auto start = chrono::high_resolution_clock::now();
#endif

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1; //cin >> t;
    while(t--) solve();

#ifdef CDuongg
   auto end = chrono::high_resolution_clock::now();
   // cout << "\n"; for(int i = 1; i <= 100; ++i) cout << '=';
   // cout << "\nExecution time: " << chrono::duration_cast<chrono::milliseconds> (end - start).count() << "[ms]" << endl;
   // cout << "Check array size pls sir" << endl;
#endif

}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14684 KB Output is correct
2 Correct 4 ms 16732 KB Output is correct
3 Correct 3 ms 14684 KB Output is correct
4 Correct 3 ms 14808 KB Output is correct
5 Correct 9 ms 31580 KB Output is correct
6 Correct 10 ms 31840 KB Output is correct
7 Correct 9 ms 31580 KB Output is correct
8 Correct 10 ms 31580 KB Output is correct
9 Correct 10 ms 31580 KB Output is correct
10 Correct 10 ms 31580 KB Output is correct
11 Correct 12 ms 31836 KB Output is correct
12 Correct 9 ms 31580 KB Output is correct
13 Correct 10 ms 31836 KB Output is correct
14 Correct 10 ms 31832 KB Output is correct
15 Correct 10 ms 31836 KB Output is correct
16 Correct 10 ms 31580 KB Output is correct
17 Correct 10 ms 31760 KB Output is correct
18 Correct 10 ms 31836 KB Output is correct
19 Correct 9 ms 31816 KB Output is correct
20 Correct 10 ms 31836 KB Output is correct
21 Correct 10 ms 31836 KB Output is correct
22 Correct 10 ms 31824 KB Output is correct
23 Correct 9 ms 31580 KB Output is correct
24 Correct 10 ms 31580 KB Output is correct
25 Correct 10 ms 31580 KB Output is correct
26 Correct 8 ms 31580 KB Output is correct
27 Correct 8 ms 31580 KB Output is correct
28 Correct 10 ms 31580 KB Output is correct
29 Correct 9 ms 31836 KB Output is correct
30 Correct 9 ms 31580 KB Output is correct
31 Correct 10 ms 31900 KB Output is correct
32 Correct 10 ms 31832 KB Output is correct
33 Correct 10 ms 31836 KB Output is correct
34 Correct 10 ms 31848 KB Output is correct
35 Correct 11 ms 31716 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 16728 KB Output is correct
2 Correct 10 ms 31692 KB Output is correct
3 Correct 10 ms 31716 KB Output is correct
4 Correct 10 ms 31668 KB Output is correct
5 Correct 346 ms 85684 KB Output is correct
6 Correct 388 ms 86584 KB Output is correct
7 Correct 434 ms 88736 KB Output is correct
8 Correct 319 ms 84848 KB Output is correct
9 Correct 279 ms 84120 KB Output is correct
10 Correct 631 ms 87884 KB Output is correct
11 Correct 458 ms 87880 KB Output is correct
12 Correct 542 ms 87088 KB Output is correct
13 Correct 426 ms 87120 KB Output is correct
14 Correct 478 ms 87156 KB Output is correct
15 Correct 521 ms 93044 KB Output is correct
16 Correct 440 ms 94528 KB Output is correct
17 Correct 450 ms 92648 KB Output is correct
18 Correct 527 ms 87872 KB Output is correct
19 Correct 445 ms 87344 KB Output is correct
20 Correct 584 ms 87596 KB Output is correct
21 Correct 453 ms 89120 KB Output is correct
22 Correct 423 ms 89792 KB Output is correct
23 Correct 468 ms 89968 KB Output is correct
24 Correct 425 ms 89112 KB Output is correct
25 Correct 382 ms 88292 KB Output is correct
26 Correct 493 ms 87552 KB Output is correct
27 Correct 402 ms 88328 KB Output is correct
28 Correct 215 ms 88640 KB Output is correct
29 Correct 196 ms 89408 KB Output is correct
30 Correct 314 ms 88380 KB Output is correct
31 Correct 324 ms 87872 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14680 KB Output is correct
2 Correct 9 ms 31576 KB Output is correct
3 Correct 10 ms 31836 KB Output is correct
4 Correct 10 ms 31836 KB Output is correct
5 Correct 416 ms 90440 KB Output is correct
6 Correct 280 ms 91036 KB Output is correct
7 Correct 267 ms 84860 KB Output is correct
8 Correct 440 ms 93696 KB Output is correct
9 Correct 429 ms 93440 KB Output is correct
10 Correct 379 ms 93476 KB Output is correct
11 Correct 358 ms 93260 KB Output is correct
12 Correct 340 ms 93056 KB Output is correct
13 Correct 316 ms 93248 KB Output is correct
14 Correct 204 ms 93504 KB Output is correct
15 Correct 211 ms 93672 KB Output is correct
16 Correct 283 ms 93132 KB Output is correct
17 Correct 410 ms 93088 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14684 KB Output is correct
2 Correct 4 ms 16732 KB Output is correct
3 Correct 3 ms 14684 KB Output is correct
4 Correct 3 ms 14808 KB Output is correct
5 Correct 9 ms 31580 KB Output is correct
6 Correct 10 ms 31840 KB Output is correct
7 Correct 9 ms 31580 KB Output is correct
8 Correct 10 ms 31580 KB Output is correct
9 Correct 10 ms 31580 KB Output is correct
10 Correct 10 ms 31580 KB Output is correct
11 Correct 12 ms 31836 KB Output is correct
12 Correct 9 ms 31580 KB Output is correct
13 Correct 10 ms 31836 KB Output is correct
14 Correct 10 ms 31832 KB Output is correct
15 Correct 10 ms 31836 KB Output is correct
16 Correct 10 ms 31580 KB Output is correct
17 Correct 10 ms 31760 KB Output is correct
18 Correct 10 ms 31836 KB Output is correct
19 Correct 9 ms 31816 KB Output is correct
20 Correct 10 ms 31836 KB Output is correct
21 Correct 10 ms 31836 KB Output is correct
22 Correct 10 ms 31824 KB Output is correct
23 Correct 9 ms 31580 KB Output is correct
24 Correct 10 ms 31580 KB Output is correct
25 Correct 10 ms 31580 KB Output is correct
26 Correct 8 ms 31580 KB Output is correct
27 Correct 8 ms 31580 KB Output is correct
28 Correct 10 ms 31580 KB Output is correct
29 Correct 9 ms 31836 KB Output is correct
30 Correct 9 ms 31580 KB Output is correct
31 Correct 10 ms 31900 KB Output is correct
32 Correct 10 ms 31832 KB Output is correct
33 Correct 10 ms 31836 KB Output is correct
34 Correct 10 ms 31848 KB Output is correct
35 Correct 11 ms 31716 KB Output is correct
36 Correct 5 ms 16728 KB Output is correct
37 Correct 10 ms 31692 KB Output is correct
38 Correct 10 ms 31716 KB Output is correct
39 Correct 10 ms 31668 KB Output is correct
40 Correct 346 ms 85684 KB Output is correct
41 Correct 388 ms 86584 KB Output is correct
42 Correct 434 ms 88736 KB Output is correct
43 Correct 319 ms 84848 KB Output is correct
44 Correct 279 ms 84120 KB Output is correct
45 Correct 631 ms 87884 KB Output is correct
46 Correct 458 ms 87880 KB Output is correct
47 Correct 542 ms 87088 KB Output is correct
48 Correct 426 ms 87120 KB Output is correct
49 Correct 478 ms 87156 KB Output is correct
50 Correct 521 ms 93044 KB Output is correct
51 Correct 440 ms 94528 KB Output is correct
52 Correct 450 ms 92648 KB Output is correct
53 Correct 527 ms 87872 KB Output is correct
54 Correct 445 ms 87344 KB Output is correct
55 Correct 584 ms 87596 KB Output is correct
56 Correct 453 ms 89120 KB Output is correct
57 Correct 423 ms 89792 KB Output is correct
58 Correct 468 ms 89968 KB Output is correct
59 Correct 425 ms 89112 KB Output is correct
60 Correct 382 ms 88292 KB Output is correct
61 Correct 493 ms 87552 KB Output is correct
62 Correct 402 ms 88328 KB Output is correct
63 Correct 215 ms 88640 KB Output is correct
64 Correct 196 ms 89408 KB Output is correct
65 Correct 314 ms 88380 KB Output is correct
66 Correct 324 ms 87872 KB Output is correct
67 Correct 3 ms 14680 KB Output is correct
68 Correct 9 ms 31576 KB Output is correct
69 Correct 10 ms 31836 KB Output is correct
70 Correct 10 ms 31836 KB Output is correct
71 Correct 416 ms 90440 KB Output is correct
72 Correct 280 ms 91036 KB Output is correct
73 Correct 267 ms 84860 KB Output is correct
74 Correct 440 ms 93696 KB Output is correct
75 Correct 429 ms 93440 KB Output is correct
76 Correct 379 ms 93476 KB Output is correct
77 Correct 358 ms 93260 KB Output is correct
78 Correct 340 ms 93056 KB Output is correct
79 Correct 316 ms 93248 KB Output is correct
80 Correct 204 ms 93504 KB Output is correct
81 Correct 211 ms 93672 KB Output is correct
82 Correct 283 ms 93132 KB Output is correct
83 Correct 410 ms 93088 KB Output is correct
84 Correct 483 ms 84808 KB Output is correct
85 Correct 370 ms 79900 KB Output is correct
86 Correct 448 ms 78952 KB Output is correct
87 Correct 635 ms 86996 KB Output is correct
88 Correct 440 ms 87160 KB Output is correct
89 Correct 615 ms 88012 KB Output is correct
90 Correct 643 ms 87692 KB Output is correct
91 Correct 578 ms 87584 KB Output is correct
92 Correct 517 ms 91440 KB Output is correct
93 Correct 485 ms 92432 KB Output is correct
94 Correct 470 ms 87944 KB Output is correct
95 Correct 614 ms 87668 KB Output is correct
96 Correct 636 ms 87664 KB Output is correct
97 Correct 507 ms 87900 KB Output is correct
98 Correct 440 ms 89684 KB Output is correct
99 Correct 452 ms 89028 KB Output is correct
100 Correct 487 ms 89592 KB Output is correct
101 Correct 423 ms 89492 KB Output is correct
102 Correct 374 ms 87744 KB Output is correct
103 Correct 374 ms 88148 KB Output is correct
104 Correct 388 ms 88416 KB Output is correct
105 Correct 246 ms 88124 KB Output is correct
106 Correct 258 ms 88332 KB Output is correct
107 Correct 345 ms 88636 KB Output is correct
108 Correct 268 ms 88904 KB Output is correct