제출 #1142272

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1142272		vastaway	Sirni (COCI17_sirni)	C++20	140 / 140	1473 ms	748144 KiB

sirni

#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;

const int M = 1e7 + 5, N = 1 << 19;

int p[N], r[N], lwrbnd[M];
vector<int> nodes;
vector<pair<int, int>> edges[M];

int ufind(int v) {
    if (v != p[v]) p[v] = ufind(p[v]);
    return p[v];
}

signed main() {
	cin.sync_with_stdio(0);
	cin.tie(0);

	int n, lim = 0;
    cin >> n;

    for (int i = 0, v; i < n; i++) {
        cin >> v;
        if (!lwrbnd[v]) {
            lwrbnd[v] = 1;
            nodes.push_back(v);
            lim = max(lim, v);
        }
    }

    iota(p, p + N, 0);
    sort(nodes.begin(), nodes.end());

    long long ans = 0;
    int cur = 0;

    for (int i = 0; i < nodes.size(); i++) {
        for (; cur <= nodes[i]; cur++) {
            lwrbnd[cur] = i;
        }
    }

    for (; cur <= lim; cur++) lwrbnd[cur] = -1;
    // for (int v : nodes) cout << v << " "; cout << "\n";
    // for (int i = 0; i < 14; i++) cout << lwrbnd[i] << " "; cout << "\n";

    for (int i = 0, v, res; i < nodes.size(); i++) {
        v = nodes[i];
        res = lwrbnd[v+1];
        if (res != -1) edges[nodes[res] % v].push_back({i, res});

        for (int vi = 2 * v; vi <= lim; vi += v) {
            res = lwrbnd[vi];
            if (res != -1) edges[nodes[res] % v].push_back({i, res});
        }
    }

    for (int i = 0; i < M; i++) {
        for (auto& [a, b] : edges[i]) {
            a = ufind(a);
            b = ufind(b);
            // cout << a << " " << b << " -> " << cost << "\n";

            if (a != b) {
                ans += i;
                if (r[a] < r[b]) swap(a, b);
                if (r[a] == r[b]) r[a]++;
                p[b] = a;
            }
        }
    }

    cout << ans << "\n";

	return 0;
}

• 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: 14 / 14
• Subtask 9: 14 / 14
• Subtask 10: 14 / 14