Submission #1245967

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245967		khoi	Sirni (COCI17_sirni)	C++20	98 / 140	4512 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) {}
    bool operator<(Edge const& o) const { return w < o.w; }
} e[40000007];

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;
    }
};

int n;
vector<int> p;
int nxt[10000005], m = 0;

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    p.resize(n);
    for (int i = 0; i < n; i++) cin >> p[i];

    sort(p.begin(), p.end());
    p.erase(unique(p.begin(), p.end()), p.end());
    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];
    int maxWeight = 0;

    for (int i = 0; i < n; i++) {
        int w1 = p[nxt[p[i]+1]] % p[i];
        e[++m] = {i, nxt[p[i]+1], w1};
        maxWeight = max(maxWeight, w1);

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

    // -------------------- COUNTING SORT --------------------
    vector<vector<Edge>> bucket(maxWeight + 1);
    for (int i = 1; i <= m; ++i)
        bucket[e[i].w].push_back(e[i]);

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

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

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

    cout << total;
}

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