제출 #1245943

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1245943		khoi	Sirni (COCI17_sirni)	C++20	98 / 140	2265 ms	851968 KiB

sirni

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

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

struct DSU {
    vector<int> par, rank;
    DSU(int n): par(n), rank(n) {
        iota(par.begin(), par.end(), 0);
    }
    int find(int u) {
        return par[u] == u ? u : par[u] = find(par[u]);
    }
    bool unite(int u, int v) {
        u = find(u); v = find(v);
        if (u == v) return false;
        if (rank[u] < rank[v]) swap(u, v);
        par[v] = u;
        if (rank[u] == rank[v]) rank[u]++;
        return true;
    }
};

const int MAX_A = 1e7 + 1;
int nxt[MAX_A], freq[MAX_A];
vector<int> p;

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n, x, maxval = 0;
    cin >> n;

    for (int i = 0; i < n; ++i) {
        cin >> x;
        if (!freq[x]) p.push_back(x);
        freq[x] = 1;
        maxval = max(maxval, x);
    }

    sort(p.begin(), p.end());  // p is already unique
    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];
    vector<Edge> edges;
    int maxWeight = 0;

    for (int i = 0; i < n; ++i) {
        int pi = p[i];
        if (pi + 1 <= mx) {
            int v = nxt[pi + 1];
            int w = p[v] % pi;
            edges.emplace_back(i, v, w);
            maxWeight = max(maxWeight, w);
        }
        for (int j = pi; j <= mx;) {
            int v = nxt[j];
            int w = p[v] % pi;
            edges.emplace_back(i, v, w);
            maxWeight = max(maxWeight, w);
            if (p[v] / pi == 0) break;
            j = (p[v] / pi) * pi + pi;
        }
    }

    // Count-based bucket sort with limited memory
    vector<vector<Edge>> bucket(maxWeight + 1);
    for (const Edge &e : edges)
        bucket[e.w].push_back(e);

    vector<Edge> sorted;
    for (int w = 0; w <= maxWeight; ++w)
        for (const Edge &e : bucket[w])
            sorted.push_back(e);

    DSU dsu(n);
    long long total = 0;
    int used = 0;
    for (const auto &[u, v, w] : sorted) {
        if (dsu.unite(u, v)) {
            total += w;
            if (++used == n - 1) break;
        }
    }

    cout << total << '\n';
}

• 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