Submission #1232535

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232535		nibert	Nile (IOI24_nile)	C++20	0 / 100	22 ms	3140 KiB

nile

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

struct DSU {
    vector<int> parent;
    DSU(int n) {
        parent.assign(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();
    vector<array<int, 3>> edges;

    // Build valid edges: only pairs where weight difference ≤ 10
    for (int w = 1; w <= 10; ++w) {
        vector<int> ids;
        for (int i = 0; i < N; ++i)
            if (W[i] == w)
                ids.push_back(i);

        for (int d = 1; d <= 10; ++d) {
            if (w + d > 10) break;
            for (int u : ids) {
                for (int v = 0; v < N; ++v) {
                    if (W[v] == w + d) {
                        edges.push_back({d, u, v});
                    }
                }
            }
        }
    }

    sort(edges.begin(), edges.end());  // sort by weight diff

    // Offline sort of queries
    int q = E.size();
    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);

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

    int ei = 0;
    for (int j = 0; j < q; ++j) {
        int maxDiff = E[ordQ[j]];

        // Add edges with weight difference ≤ D
        while (ei < edges.size() && edges[ei][0] <= maxDiff) {
            int u = edges[ei][1];
            int v = edges[ei][2];
            if (!dsu.same(u, v)) {
                // Replace cost A[u] + A[v] with B[u] + B[v]
                total -= (A[u] + A[v]);
                total += (B[u] + B[v]);
                dsu.unite(u, v);
            }
            ++ei;
        }

        res[ordQ[j]] = 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