Submission #931109

#	Time	Username	Problem	Language	Result	Execution time	Memory
931109		alextodoran	Two Currencies (JOI23_currencies)	C++17	100 / 100	2234 ms	34552 KiB

currencies

/**
 _  _   __  _ _ _  _  _ _
 |a  ||t  ||o    d | |o  |
| __    _| | _ | __|  _ |
| __ |/_  | __  /__\ / _\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N_MAX = 100000;
const int M_MAX = 100000;
const int Q_MAX = 100000;
const int SILVER_MAX = 1000000000;
const int LOG2_N = 17;

int N, M, Q;
int edge_u[N_MAX + 2], edge_v[N_MAX + 2];
vector <int> adj[N_MAX + 2];
int cpt_edge[M_MAX + 2], cpt_silver[M_MAX + 2];
int qry_start[Q_MAX + 2], qry_finish[Q_MAX + 2];
int qry_gold[Q_MAX + 2]; ll qry_silver[Q_MAX + 2];

int parent[N_MAX + 2], depth[N_MAX + 2];;
int label[N_MAX + 2], max_label[N_MAX + 2];
int curr_label;

void dfs (int u) {
    label[u] = ++curr_label;
    for (int v : adj[u]) {
        if (v != parent[u]) {
            parent[v] = u;
            depth[v] = depth[u] + 1;
            dfs(v);
        }
    }
    max_label[u] = curr_label;
}

int ancestor[N_MAX + 2][LOG2_N];

int find_ancestor (int u, int k) {
    for (int t = 0; t < LOG2_N; t++) {
        if ((k >> t) & 1) {
            u = ancestor[u][t];
        }
    }
    return u;
}

int find_lca (int u, int v) {
    if (depth[u] > depth[v]) {
        u = find_ancestor(u, depth[u] - depth[v]);
    }
    if (depth[v] > depth[u]) {
        v = find_ancestor(v, depth[v] - depth[u]);
    }
    if (u == v) {
        return u;
    }
    for (int t = LOG2_N - 1; t >= 0; t--) {
        if (ancestor[u][t] != ancestor[v][t]) {
            u = ancestor[u][t];
            v = ancestor[v][t];
        }
    }
    return parent[u];
}

int lower[Q_MAX + 2], higher[Q_MAX + 2];
int mid[Q_MAX + 2]; ll sum[Q_MAX + 2]; int cnt[Q_MAX + 2];

int cpt_order[M_MAX + 2];
int qry_order[Q_MAX + 2];

ll Fenwick_sum[N_MAX + 2]; int Fenwick_cnt[N_MAX + 2];

void update (int pos, int val) {
    for (int i = pos; i <= N; i += i & -i) {
        Fenwick_sum[i] += val;
        Fenwick_cnt[i] += (val > 0 ? +1 : -1);
    }
}
void update (int l, int r, int val) {
    update(l, +val); update(r + 1, -val);
}
pair <ll, int> query (int pos) {
    ll sum = 0; int cnt = 0;
    for (int i = pos; i >= 1; i -= i & -i) {
        sum += Fenwick_sum[i];
        cnt += Fenwick_cnt[i];
    }
    return make_pair(sum, cnt);
}

void step () {
    iota(cpt_order + 1, cpt_order + M + 1, 1);
    iota(qry_order + 1, qry_order + Q + 1, 1);
    sort(cpt_order + 1, cpt_order + M + 1, [&] (const int &i, const int &j) {
        return cpt_silver[i] < cpt_silver[j];
    });
    sort(qry_order + 1, qry_order + Q + 1, [&] (const int &i, const int &j) {
        return mid[i] < mid[j];
    });
    fill(Fenwick_sum + 1, Fenwick_sum + N + 1, 0);
    fill(Fenwick_cnt + 1, Fenwick_cnt + N + 1, 0);
    for (int i = 1, j = 0; i <= Q && mid[qry_order[i]] != INT_MAX; i++) {
        while (j + 1 <= M && cpt_silver[cpt_order[j + 1]] <= mid[qry_order[i]]) {
            int e = cpt_edge[cpt_order[++j]];
            update(label[edge_v[e]], max_label[edge_v[e]], cpt_silver[cpt_order[j]]);
        }
        int u = qry_start[qry_order[i]], v = qry_finish[qry_order[i]];
        int lca = find_lca(u, v);
        ll sum_u; int cnt_u; tie(sum_u, cnt_u) = query(label[u]);
        ll sum_v; int cnt_v; tie(sum_v, cnt_v) = query(label[v]);
        ll sum_lca; int cnt_lca; tie(sum_lca, cnt_lca) = query(label[lca]);
        sum[qry_order[i]] = sum_u + sum_v - 2 * sum_lca;
        cnt[qry_order[i]] = cnt_u + cnt_v - 2 * cnt_lca;
    }
}

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

    cin >> N >> M >> Q;
    for (int i = 1; i <= N - 1; i++) {
        cin >> edge_u[i] >> edge_v[i];
        adj[edge_u[i]].push_back(edge_v[i]);
        adj[edge_v[i]].push_back(edge_u[i]);
    }
    dfs(1);
    for (int u = 1; u <= N; u++) {
        ancestor[u][0] = parent[u];
    }
    for (int t = 1; t < LOG2_N; t++) {
        for (int u = 1; u <= N; u++) {
            ancestor[u][t] = ancestor[ancestor[u][t - 1]][t - 1];
        }
    }
    for (int i = 1; i <= N - 1; i++) {
        if (edge_u[i] != parent[edge_v[i]]) {
            swap(edge_u[i], edge_v[i]);
        }
    }
    for (int i = 1; i <= M; i++) {
        cin >> cpt_edge[i] >> cpt_silver[i];
    }
    for (int i = 1; i <= Q; i++) {
        cin >> qry_start[i] >> qry_finish[i];
        cin >> qry_gold[i] >> qry_silver[i];
        lower[i] = 0; higher[i] = SILVER_MAX;
    }
    while (true) {
        bool done = true;
        for (int i = 1; i <= Q; i++) {
            if (lower[i] < higher[i]) {
                done = false;
                mid[i] = (lower[i] + higher[i] + 1) / 2;
            } else {
                mid[i] = INT_MAX; // done
            }
        }
        if (done == true) {
            break;
        }
        step();
        for (int i = 1; i <= Q; i++) {
            if (mid[i] != INT_MAX) {
                if (sum[i] <= qry_silver[i]) {
                    lower[i] = mid[i];
                } else {
                    higher[i] = mid[i] - 1;
                }
            }
        }
    }
    for (int i = 1; i <= Q; i++) {
        mid[i] = lower[i];
    }
    step();
    fill(Fenwick_sum + 1, Fenwick_sum + N + 1, 0);
    fill(Fenwick_cnt + 1, Fenwick_cnt + N + 1, 0);
    for (int i = 1; i <= M; i++) {
        int e = cpt_edge[i];
        update(label[edge_v[e]], max_label[edge_v[e]], cpt_silver[i]);
    }
    for (int i = 1; i <= Q; i++) {
        int u = qry_start[i], v = qry_finish[i];
        int lca = find_lca(u, v);
        int total_cpt = query(label[u]).second + query(label[v]).second - 2 * query(label[lca]).second;
        int with_silver = cnt[i];
        if (with_silver < total_cpt) {
            with_silver += min((ll) (total_cpt - with_silver), (qry_silver[i] - sum[i]) / (mid[i] + 1));
        }
        int with_gold = total_cpt - with_silver;
        cout << (with_gold <= qry_gold[i] ? qry_gold[i] - with_gold : -1) << "\n";
    }

    return 0;
}

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