Submission #1232613

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232613		nibert	Nile (IOI24_nile)	C++20	100 / 100	75 ms	10940 KiB

nile

#include "bits/stdc++.h"
#include "nile.h"
using namespace std;

const int INF = 1e9;

// Augmented DSU: we store more info per component (like min cost and index)
struct DSU {
    vector<int> e;           // parent array (negative means root and holds size)
    vector<int> c;           // c[i] = A[i] - B[i]
    vector<int> mni;         // smallest index in component (for parity decisions)
    vector<array<int, 3>> mnc; // mnc[i][0/1/2] = min cost for parity 0/1/unpaired
    long long tot = 0;       // extra cost to add to baseline

    DSU(int n, vector<int> c) : e(n, -1), c(c), mni(n), mnc(n) {
        for (int i = 0; i < n; ++i) {
            mni[i] = i;
            mnc[i] = {INF, INF, INF};  // large default
            mnc[i][i % 2] = c[i];      // set A[i]-B[i] based on index parity
            tot += c[i];               // initially all artifacts go alone
        }
    }

    int find(int x) { return e[x] < 0 ? x : e[x] = find(e[x]); }
    int size(int x) { return -e[find(x)]; }

    // Computes extra cost for a group rooted at x
    int cost(int x) {
        int idx = mnc[x][mni[x] % 2] < mnc[x][2] ? (mni[x] % 2) : 2;
        return mnc[x][idx] * (size(x) % 2);  // pay only if group has odd size
    }

    bool join(int i, int j) {
        int x = find(i), y = find(j);
        if (x == y) {
            tot -= cost(x); // remove old cost
            mnc[x][2] = min(mnc[x][2], c[(i + j) / 2]); // update fallback
            tot += cost(x); // add new cost
            return false;
        }
        tot -= cost(x);
        tot -= cost(y);
        if (e[x] > e[y]) swap(x, y); // merge small into large
        e[x] += e[y];
        e[y] = x;
        for (int p = 0; p < 3; ++p) mnc[x][p] = min(mnc[x][p], mnc[y][p]);
        mni[x] = min(mni[x], mni[y]);
        tot += cost(x);
        return true;
    }
};

// Main function using offline queries and edge merging
vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {
    int n = W.size(), q = E.size();

    // Sort artifacts by weight
    vector<int> ordW(n);
    iota(ordW.begin(), ordW.end(), 0);
    sort(ordW.begin(), ordW.end(), [&](int i, int j) {
        return W[i] < W[j];
    });

    // Sort queries by D
    vector<int> ordE(q);
    iota(ordE.begin(), ordE.end(), 0);
    sort(ordE.begin(), ordE.end(), [&](int i, int j) {
        return E[i] < E[j];
    });

    vector<int> w(n), c(n);  // remapped weights and A-B costs
    for (int i = 0; i < n; ++i) {
        int j = ordW[i];
        w[i] = W[j];
        c[i] = A[j] - B[j];
    }

    // Precompute edges: (weight difference, index1, index2)
    vector<array<int, 3>> edges;
    for (int i = 0; i < n; ++i) {
        if (i + 1 < n) edges.push_back({w[i + 1] - w[i], i, i + 1});
        if (i + 2 < n) edges.push_back({w[i + 2] - w[i], i, i + 2});
    }
    sort(edges.rbegin(), edges.rend()); // descending for efficient pop_back()

    // Initialize DSU and base cost (everyone goes in a boat together: sum B[i])
    DSU d(n, c);
    vector<long long> R(q, accumulate(B.begin(), B.end(), 0LL));

    // Process queries in increasing order of D
    for (int i = 0; i < q; ++i) {
        while (!edges.empty() && edges.back()[0] <= E[ordE[i]]) {
            auto [_, x, y] = edges.back(); edges.pop_back();
            d.join(x, y); // merge if allowed
        }
        R[ordE[i]] += d.tot; // add extra cost of lone artifacts in odd groups
    }

    return R;
}

• Subtask 0: 0 / 0
• Subtask 1: 6 / 6
• Subtask 2: 13 / 13
• Subtask 3: 17 / 17
• Subtask 4: 11 / 11
• Subtask 5: 20 / 20
• Subtask 6: 15 / 15
• Subtask 7: 18 / 18