Submission #1275152

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275152		vk3601h	Sirni (COCI17_sirni)	C++20	0 / 140	285 ms	85740 KiB

sirni

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <climits>

using namespace std;

const int MAX_VAL = 10000000;
const int T = 1000;

vector<int> parent;

int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]);
    }
    return parent[x];
}

void unite(int x, int y) {
    x = find(x);
    y = find(y);
    if (x != y) {
        parent[y] = x;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    vector<int> P(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());
    int m = P.size();

    if (m <= 1) {
        cout << 0 << endl;
        return 0;
    }

    if (P[0] == 1) {
        cout << 0 << endl;
        return 0;
    }

    vector<int> next(MAX_VAL + 2, 0);
    vector<int> pos(MAX_VAL + 1, -1);

    for (int i = 0; i < m; i++) {
        pos[P[i]] = i;
    }

    for (int i = MAX_VAL; i >= 1; i--) {
        next[i] = next[i + 1];
        if (pos[i] != -1) {
            next[i] = i;
        }
    }

    parent.resize(m);
    for (int i = 0; i < m; i++) {
        parent[i] = i;
    }

    for (int i = 0; i < m; i++) {
        int a = P[i];
        for (int k = 2; a * k <= MAX_VAL; k++) {
            int target = a * k;
            if (next[target] == target) {
                int j = pos[target];
                if (j != -1) {
                    unite(i, j);
                }
            }
        }
    }

    int components = 0;
    for (int i = 0; i < m; i++) {
        if (find(i) == i) {
            components++;
        }
    }

    if (components == 1) {
        cout << 0 << endl;
        return 0;
    }

    vector<tuple<int, int, int>> edges;

    for (int i = 0; i < m && P[i] <= T; i++) {
        int a = P[i];
        for (int k = 1; a * k <= MAX_VAL; k++) {
            int L = a * k;
            int R = a * (k + 1) - 1;
            if (L > MAX_VAL) break;
            if (next[L] == 0) continue;
            if (next[L] > R) continue;
            int b = next[L];
            int j = pos[b];
            if (j == -1) continue;
            if (find(i) != find(j)) {
                edges.push_back({i, j, b - L});
            }
        }
    }

    for (int i = 0; i < m - 1; i++) {
        if (find(i) != find(i + 1)) {
            edges.push_back({i, i + 1, P[i + 1] - P[i]});
        }
    }

    sort(edges.begin(), edges.end(), [](const auto& a, const auto& b) {
        return get<2>(a) < get<2>(b);
    });

    long long ans = 0;
    for (const auto& e : edges) {
        int u = get<0>(e);
        int v = get<1>(e);
        int w = get<2>(e);
        if (find(u) != find(v)) {
            ans += w;
            unite(u, v);
            components--;
            if (components == 1) break;
        }
    }

    cout << ans << endl;

    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