Submission #1211388

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211388		sula2	Nile (IOI24_nile)	C++20	Compilation error	0 ms	0 KiB

nile

#include <bits/stdc++.h>
#define all(a) a.begin(), a.end()
#define popcount(x) __builtin_popcountll(x)
using namespace std;
using namespace chrono;

struct DSU {
    vector<int> par, size, mn_odd, mn_even, ans, costs;
    long long sum = 0;

    DSU(int n, vector<int> C) : par(n), size(n, 1), mn_odd(C), ans(C), costs(C) {
        mn_even.assign(n, INT_MAX);
        sum = accumulate(all(C), 0LL);
        iota(all(par), 0);
    }

    int find(int u) {
        return par[u] == u ? u : par[u] = find(par[u]);
    }

    void add(int u) {
        u = find(u);
        if (size[u] & 1) sum += ans[u];
    }

    void subtract(int u) {
        u = find(u);
        if (size[u] & 1) sum -= ans[u];
    }

    void merge(int u, int v) {
        if (v-u == 1) {
            u = find(u), v = find(v);
            subtract(u);
            subtract(v);
            if (size[u] & 1) {
                swap(mn_odd[v], mn_even[v]);
            }
            mn_odd[u] = min(mn_odd[u], mn_odd[v]);
            mn_even[u] = min(mn_even[u], mn_even[v]);
            ans[u] = min(ans[u], mn_odd[u]);
            ans[u] = min(ans[u], ans[v]);
            par[v] = u;
            size[u] += size[v];
            add(u);
        } else {
            int r = find(u);
            subtract(r);
            ans[r] = min(ans[r], costs[u+1]);
            add(r);
        }
    }
};

vector<long long> calculate_costs(
        vector<int> W, vector<int> A,
        vector<int> B, vector<int> E
        ) {
    int n = W.size(), q = E.size();
    vector<int> ind_W(n);
    iota(all(ind_W), 0);
    sort(all(ind_W), [&](int i, int j) { return W[i] < W[j]; });
    vector<int> new_W(n), C(n);
    for (int i = 0; i < n; i++) {
        new_W[i] = W[ind_W[i]];
        C[i] = A[ind_W[i]] - B[ind_W[i]];
    }
    swap(new_W, W);
    vector<int> ind_E(q);
    iota(all(ind_E), 0);
    sort(all(ind_E), [&](int i, int j) { return E[i] < E[j]; });
    vector<array<int, 3>> edges;
    for (int i = 0; i < n-1; i++) {
        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(all(edges));

    DSU D(n, C);
    int ptr = 0;
    long long sum_B = accumulate(all(B), 0LL);
    vector<long long> ans(q);
    for (int i : ind_E) {
        while (ptr < edges.size() && edges[ptr][0] <= E[i]) {
            int u = edges[ptr][1];
            int v = edges[ptr][2];
            D.merge(u, v);
            ptr++;
        }
        ans[i] = D.sum + sum_B;
    }

    return ans;
}

int main() {
    vector<int> W = {15, 12, 2, 10, 21};
    vector<int> A = {5, 4, 5, 6, 3};
    vector<int> B = {1, 2, 2, 3, 2};
    vector<int> E = {5, 9, 1};
    for (auto x : calculate_costs(W, A, B, E)) cout << x << "\n";
}

Compilation message (stderr)

/usr/bin/ld: /tmp/cczuZkjf.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccWvb4Dm.o:nile.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status