Submission #1310146

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310146		Hostek	Two Currencies (JOI23_currencies)	C++20	100 / 100	803 ms	46560 KiB

currencies

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

#include <bits/stdc++.h>

constexpr int MAXN = 100005;
constexpr int SIZIK = 200005;
constexpr int L = 18;

typedef long long ll;

std::vector<std::pair<int, int>> adj[SIZIK];
int edge_to_node[SIZIK];
int checkpoints_on_edge[SIZIK];

int depth[SIZIK], pre[SIZIK], post[SIZIK], timer = 0;
int up[SIZIK][L + 1];
int static_path_cnt[SIZIK][L + 1];

ll bit_cost[SIZIK];
int bit_cnt[SIZIK];

struct Query {
    int s, t, x;
    ll y;
};
std::vector<Query> queries;
std::vector<int> mids[SIZIK];
std::array<int, 2> q_range[SIZIK];
int silver_covered_cnt[SIZIK];
ll final_gold_ans[SIZIK];

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

void subtree_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 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];

    static_path_cnt[v][0] = (edge_idx != -1 ? checkpoints_on_edge[edge_idx] : 0);
    for (int i = 1; i <= L; ++i) {
        static_path_cnt[v][i] = static_path_cnt[v][i - 1] + static_path_cnt[up[v][i - 1]][i - 1];
    }

    for (auto& edge : adj[v]) {
        if (edge.first != p) {
            dfs(edge.first, v, edge.second);
        }
    }
    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 get_static_cnt_up(int u, int l) {
    int res = 0;
    for (int i = L; i >= 0; --i) {
        if (!is_ancestor(up[u][i], l)) {
            res += static_path_cnt[u][i];
            u = up[u][i];
        }
    }
    if (u != l) res += static_path_cnt[u][0];
    return res;
}

int get_total_static(int u, int v) {
    int l = lca(u, v);
    return get_static_cnt_up(u, l) + get_static_cnt_up(v, l);
}

void clear_bits() {
    std::fill(bit_cost, bit_cost + timer + 2, 0);
    std::fill(bit_cnt, bit_cnt + timer + 2, 0);
}

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

    for (int i = 1; i < n; i++) {
        int u, v;
        std::cin >> u >> v;
        adj[u].push_back({v, i});
        adj[v].push_back({u, i});
    }

    std::vector<std::pair<int, int>> CP(m);
    for (int i = 0; i < m; i++) {
        std::cin >> CP[i].first >> CP[i].second;
        checkpoints_on_edge[CP[i].first]++;
    }

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

    dfs(1, 1, -1);

    queries.resize(q + 1);
    for (int i = 1; i <= q; i++) {
        std::cin >> queries[i].s >> queries[i].t >> queries[i].x >> queries[i].y;

        int total = get_total_static(queries[i].s, queries[i].t);
        final_gold_ans[i] = (ll)queries[i].x - total;

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

    int remaining_queries = q;

    while (remaining_queries > 0) {
        clear_bits();

        for (int i = 0; i <= m; i++) {
            if (i > 0) {
                int edge_idx = CP[i - 1].first;
                int cost = CP[i - 1].second;
                int u = edge_to_node[edge_idx];
                subtree_update(u, cost, 1);
            }

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

            for (int q_idx : mids[i]) {
                const auto& Q = queries[q_idx];
                int l = lca(Q.s, Q.t);

                ll path_cost = query_cost(pre[Q.s]) + query_cost(pre[Q.t]) - 2 * query_cost(pre[l]);
                int path_cnt = query_cnt(pre[Q.s]) + query_cnt(pre[Q.t]) - 2 * query_cnt(pre[l]);

                if (path_cost <= Q.y) {
                    silver_covered_cnt[q_idx] = path_cnt;
                    q_range[q_idx][0] = i + 1;
                } else {
                    q_range[q_idx][1] = i - 1;
                }

                int L_Range = q_range[q_idx][0];
                int R_Range = q_range[q_idx][1];

                if (L_Range <= R_Range) {
                    mids[(L_Range + R_Range) / 2].push_back(q_idx);
                } else {
                    remaining_queries--;
                }
            }
            mids[i].clear();
        }
    }

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

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

    solve();

    return 0;
}

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