Submission #1245974

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245974		khoi	Sirni (COCI17_sirni)	C++20	0 / 140	5086 ms	832 KiB

sirni

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

const int MAXN = 100000;
const int MAXV = 10000000;
const int MAXE = 40000000;

struct Edge {
    int u, v, w;
    bool operator<(const Edge &o) const {
        return w < o.w;
    }
};

Edge e[MAXE];
int m = 0;

int par[MAXN+5], rnk_[MAXN+5];
int pval[MAXN+5], nxt_idx[MAXV+5];
int n;

void dsu_init(int N) {
    for (int i = 0; i < N; ++i) {
        par[i] = i;
        rnk_[i] = 0;
    }
}

int dsu_find(int x) {
    return par[x] == x ? x : par[x] = dsu_find(par[x]);
}
bool dsu_union(int a, int b) {
    a = dsu_find(a);
    b = dsu_find(b);
    if (a == b) return false;
    if (rnk_[a] < rnk_[b]) swap(a, b);
    par[b] = a;
    if (rnk_[a] == rnk_[b]) ++rnk_[a];
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> pval[i];
    }
    sort(pval, pval + n);
    n = unique(pval, pval + n) - pval;

    // build nxt_idx array
    for (int i = 0; i < n - 1; ++i) {
        int cur = pval[i];
        int nxtv = pval[i+1];
        for (int x = cur; x < nxtv; ++x) {
            nxt_idx[x] = i + 1;
            x = (pval[nxt_idx[x]] / pval[i]) * pval[i] - 1;
        }
        nxt_idx[cur] = i;
    }
    nxt_idx[pval[n-1]] = n-1;
    int mx = pval[n-1];

    // generate edges
    for (int i = 0; i < n; ++i) {
        // neighbor +1
        int j = nxt_idx[pval[i] + 1 > mx ? mx : pval[i] + 1];
        e[++m] = {i, j, pval[j] % pval[i]};
        // multiples
        for (int x = pval[i]; x <= mx; x += pval[i]) {
            int idx = nxt_idx[x];
            e[++m] = {i, idx, pval[idx] % pval[i]};
            x = (pval[idx] / pval[i]) * pval[i];
        }
    }

    sort(e + 1, e + 1 + m);

    dsu_init(n);
    long long total = 0;
    int cnt = 0;
    for (int i = 1; i <= m; ++i) {
        if (dsu_union(e[i].u, e[i].v)) {
            total += e[i].w;
            if (++cnt == n - 1) break;
        }
    }
    cout << total;
    return 0;
}

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