Submission #1245938

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245938		dangkhoi	Sirni (COCI17_sirni)	C++20	84 / 140	1679 ms	851968 KiB

sirni

#include <bits/stdc++.h>
using namespace std;

struct Edge {
    int u, v;
    int w;
    Edge(int _u, int _v, int _w): u(_u), v(_v), w(_w) {}
    Edge(): u(0), v(0), w(0) {}
};

struct DSU {
    vector<int> par, rank;
    DSU(int n): par(n + 1), rank(n + 1) {}
    void make_set(int u) {
        par[u] = u;
        rank[u] = 0;
    }
    int find_set(int v) {
        return par[v] == v ? v : par[v] = find_set(par[v]);
    }
    bool union_set(int u, int v) {
        u = find_set(u);
        v = find_set(v);
        if (u != v) {
            if (rank[u] < rank[v]) swap(u, v);
            par[v] = u;
            if (rank[u] == rank[v]) rank[u]++;
            return true;
        }
        return false;
    }
};

const int MAX_A = 1e7 + 1;
int nxt[MAX_A], freq[MAX_A] = {}, m = 0;
Edge* e = new Edge[40000007]; // big heap array

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    int n;
    cin >> n;
    vector<int> input(n);
    int maxval = 0;
    for (int i = 0; i < n; i++) {
        cin >> input[i];
        freq[input[i]] = 1;
        maxval = max(maxval, input[i]);
    }

    // ---- Counting Sort with Unique Filtering ----
    vector<int> p;
    for (int i = 0; i <= maxval; ++i)
        if (freq[i]) p.push_back(i);
    n = p.size();
    // ---------------------------------------------

    for (int i = 0; i < n - 1; i++) {
        nxt[p[i]] = i;
        for (int j = p[i] + 1; j < p[i + 1]; j++) {
            nxt[j] = i + 1;
        }
    }
    nxt[p[n - 1]] = n - 1;

    int mx = p[n - 1];

    for (int i = 0; i < n; i++) {
        if (p[i] + 1 <= mx)
            e[++m] = {i, nxt[p[i] + 1], p[nxt[p[i] + 1]] % p[i]};
        for (int j = p[i]; j <= mx;) {
            int v = nxt[j];
            e[++m] = {i, v, p[v] % p[i]};
            if (p[v] / p[i] == 0) break;
            j = (p[v] / p[i]) * p[i] + p[i];
        }
    }

    // -------- COUNTING SORT ON EDGE WEIGHTS --------
    const int MAX_W = 1e7 + 1;
    vector<vector<Edge>> bucket(MAX_W);
    for (int i = 1; i <= m; ++i)
        bucket[e[i].w].push_back(e[i]);

    int idx = 1;
    for (int w = 0; w < MAX_W; ++w)
        for (Edge &edge : bucket[w])
            e[idx++] = edge;
    // ------------------------------------------------

    DSU d(n);
    for (int i = 0; i < n; i++) d.make_set(i);

    int total = 0, count = 0;
    for (int i = 1; i <= m; i++) {
        auto [u, v, w] = e[i];
        if (d.union_set(u, v)) {
            total += w;
            if (++count == n - 1) break;
        }
    }

    cout << total << '\n';
    delete[] e;
}

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 0 / 14
• Subtask 7: 14 / 14
• Subtask 8: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14