Submission #1232544

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232544		nibert	Nile (IOI24_nile)	C++20	0 / 100	2095 ms	13844 KiB

nile

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

struct DSU {
    vector<int> parent;
    DSU(int n) : parent(n, -1) {}

    int find(int x) {
        if (parent[x] < 0) return x;
        return parent[x] = find(parent[x]);
    }

    bool same(int x, int y) {
        return find(x) == find(y);
    }

    void unite(int x, int y) {
        x = find(x); y = find(y);
        if (x == y) return;
        if (parent[x] > parent[y]) swap(x, y);
        parent[x] += parent[y];
        parent[y] = x;
    }
};

vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {
    int N = W.size();
    int Q = E.size();

    // Sort artifact indices 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];
    });

    // Build edges between sorted neighbors
    vector<array<int, 3>> edges;
    for (int i = 0; i + 1 < N; ++i) {
        int u = ordW[i], v = ordW[i + 1];
        edges.push_back({abs(W[u] - W[v]), u, v});
    }
    for (int i = 0; i + 2 < N; ++i) {
        int u = ordW[i], v = ordW[i + 2];
        edges.push_back({abs(W[u] - W[v]), u, v});
    }
    sort(edges.begin(), edges.end());

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

    vector<long long> res(Q);
    DSU dsu(N);

    // Keep track of which component has been merged and its cost
    vector<bool> merged(N, false);
    vector<vector<int>> groups(N); // group[i] holds nodes in component with root i
    for (int i = 0; i < N; ++i) groups[i] = {i};

    // Initial total cost: send all artifacts alone
    long long total = 0;
    for (int i = 0; i < N; ++i) total += A[i];

    int ei = 0;
    for (int qi = 0; qi < Q; ++qi) {
        int d = E[ordQ[qi]];

        while (ei < edges.size() && edges[ei][0] <= d) {
            int u = edges[ei][1], v = edges[ei][2];
            int ru = dsu.find(u);
            int rv = dsu.find(v);
            if (ru != rv) {
                // Remove old cost
                long long oldCost = 0;
                if (!merged[ru]) {
                    if (groups[ru].size() % 2 == 0) {
                        for (int x : groups[ru]) oldCost += B[x];
                    } else {
                        long long minExtra = LLONG_MAX;
                        for (int x : groups[ru]) {
                            oldCost += B[x];
                            minExtra = min(minExtra, 1LL * (A[x] - B[x]));
                        }
                        oldCost += minExtra;
                    }
                }
                if (!merged[rv]) {
                    if (groups[rv].size() % 2 == 0) {
                        for (int x : groups[rv]) oldCost += B[x];
                    } else {
                        long long minExtra = LLONG_MAX;
                        for (int x : groups[rv]) {
                            oldCost += B[x];
                            minExtra = min(minExtra, 1LL * (A[x] - B[x]));
                        }
                        oldCost += minExtra;
                    }
                }

                dsu.unite(u, v);
                int newRoot = dsu.find(u);
                if (newRoot == rv) swap(ru, rv);  // make ru the new root
                for (int x : groups[rv]) groups[ru].push_back(x);
                groups[rv].clear();
                merged[ru] = true;

                // Add new cost
                long long newCost = 0;
                if (groups[ru].size() % 2 == 0) {
                    for (int x : groups[ru]) newCost += B[x];
                } else {
                    long long minExtra = LLONG_MAX;
                    for (int x : groups[ru]) {
                        newCost += B[x];
                        minExtra = min(minExtra, 1LL * (A[x] - B[x]));
                    }
                    newCost += minExtra;
                }

                total -= oldCost;
                total += newCost;
            }
            ++ei;
        }

        res[ordQ[qi]] = total;
    }

    return res;
}

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