Submission #1310141

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310141		Hostek	Two Currencies (JOI23_currencies)	C++20	0 / 100	4 ms	1340 KiB

currencies

// https://oj.uz/problem/view/JOI23_currencies

#include <bits/stdc++.h>

using namespace std;

constexpr int sizik = 200005, L = 18;

#define ar std::array
#define vec std::vector

typedef long long ll;

vec<ar<int, 2>> kra[sizik];
ar<int, 2> kraw_[sizik];
ll ans[sizik];
int silver_cnt[sizik];

int depth[sizik], pre[sizik], post[sizik], timer = 0;
ar<int, L + 1> up[sizik];
ar<int, L + 1> IleNaG[sizik];

int edge_to_node[sizik];
int Ile[sizik];

ll bit_cost[sizik];
int bit_cnt[sizik];

void bit_update(int idx, ll val_cost, int val_cnt) {
    for (; idx < sizik; idx += idx & -idx) {
        bit_cost[idx] += val_cost;
        bit_cnt[idx] += val_cnt;
    }
}

void range_update(int u, ll val_cost, int val_cnt) {
    bit_update(pre[u], val_cost, val_cnt);
    bit_update(post[u] + 1, -val_cost, -val_cnt);
}

ll query_cost(int idx) {
    ll sum = 0;
    for (; idx > 0; idx -= idx & -idx)
        sum += bit_cost[idx];
    return sum;
}

int query_cnt(int idx) {
    int sum = 0;
    for (; idx > 0; idx -= idx & -idx)
        sum += bit_cnt[idx];
    return sum;
}

void DFS(int v, int p, int czk, int edge_idx) {
    depth[v] = depth[p] + 1;
    pre[v] = ++timer;

    if (edge_idx != -1) edge_to_node[edge_idx] = v;

    up[v][0] = p;
    for (int i = 1; i <= L; ++i)
        up[v][i] = up[up[v][i - 1]][i - 1];

    IleNaG[v][0] = czk;
    for (int i = 1; i <= L; ++i) {
        IleNaG[v][i] = IleNaG[v][i - 1] + IleNaG[up[v][i - 1]][i - 1];
    }

    for (const auto& [u, i] : kra[v]) {
        if (u != p) {
            DFS(u, v, Ile[i], i);
        }
    }
    post[v] = timer;
}

bool is_ancestor(int u, int v) {
    return pre[u] <= pre[v] && post[u] >= post[v];
}

int lca(int u, int v) {
    if (is_ancestor(u, v)) return u;
    if (is_ancestor(v, u)) return v;
    for (int i = L; i >= 0; --i) {
        if (!is_ancestor(up[u][i], v)) u = up[u][i];
    }
    return up[u][0];
}

int gn_helper(int v, int l) {
    int wyn = 0;
    for (int i = L; i >= 0; --i) {
        if (!is_ancestor(up[v][i], l)) {
            wyn += IleNaG[v][i];
            v = up[v][i];
        }
    }
    if (v != l) wyn += IleNaG[v][0];
    return wyn;
}

int getNum(int v1, int v2) {
    int l = lca(v1, v2);
    return gn_helper(v1, l) + gn_helper(v2, l);
}

vec<int> mids[sizik];
ar<int, 2> pk[sizik];

int midFunc(int gp, int gk) {
    return (gp + gk) / 2;
}

void clear_bits() {
    for (int i = 0; i <= timer + 1; ++i) {
        bit_cost[i] = 0;
        bit_cnt[i] = 0;
    }
}

void solve() {
    int n, m, q;
    std::cin >> n >> m >> q;

    for (int i = 1; i <= n - 1; i++) {
        auto& [a, b] = kraw_[i];
        std::cin >> a >> b;
        kra[a].push_back({b, i});
        kra[b].push_back({a, i});
    }

    std::vector<ar<int, 2>> CP(m);
    for (auto& [edge_idx, cost] : CP) {
        std::cin >> edge_idx >> cost;
        Ile[edge_idx]++;
    }

    std::sort(CP.begin(), CP.end(), [](const ar<int, 2>& a, const ar<int, 2>& b) { return a[1] < b[1]; });

    DFS(1, 1, 0, -1);

    std::vector<ar<int, 4>> mieszkancy(q + 1);

    for (int i = 1; i <= q; ++i) {
        auto& [s, t, x, y] = mieszkancy[i];
        std::cin >> s >> t >> x >> y;

        int total_checkpoints = getNum(s, t);
        ans[i] = (ll)x - total_checkpoints;

        pk[i] = {0, m};
        mids[(0 + m) / 2].push_back(i);
    }

    int zostalo = q;

    while (zostalo) {
        clear_bits();

        for (int i = 0; i <= m; i++) {
            if (i > 0) {
                int edge = CP[i - 1][0];
                int cost = CP[i - 1][1];
                int u = edge_to_node[edge];
                range_update(u, cost, 1);
            }

            if (mids[i].empty()) continue;

            for (const auto u : mids[i]) {
                auto& [p, k] = pk[u];

                int s = mieszkancy[u][0];
                int t = mieszkancy[u][1];
                int l = lca(s, t);
                ll y_lim = mieszkancy[u][3];

                ll current_cost = query_cost(pre[s]) + query_cost(pre[t]) - 2 * query_cost(pre[l]);
                int current_cnt = query_cnt(pre[s]) + query_cnt(pre[t]) - 2 * query_cnt(pre[l]);

                if (current_cost <= y_lim) {
                    silver_cnt[u] = current_cnt;
                    p = i + 1;
                } else {
                    k = i - 1;
                }

                if (p <= k) {
                    mids[midFunc(p, k)].push_back(u);
                } else {
                    zostalo--;
                }
            }
            mids[i].clear();
        }
    }

    for (int i = 1; i <= q; i++) {
        ll res = ans[i] + silver_cnt[i];
        std::cout << std::max(-1LL, res) << '\n';
    }
}

int32_t main() {
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);

    solve();

    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 28
• Subtask 3: 0 / 30
• Subtask 4: 0 / 32