Submission #1309929

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309929		dodjing	Sirni (COCI17_sirni)	C++20	0 / 140	82 ms	8368 KiB

sirni

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

struct DSU {
    vector<int> p, r;
    DSU(int n) : p(n), r(n,0) {
        iota(p.begin(), p.end(), 0);
    }
    int find(int x) {
        return p[x] == x ? x : p[x] = find(p[x]);
    }
    bool unite(int a, int b) {
        a = find(a); b = find(b);
        if (a == b) return false;
        if (r[a] < r[b]) swap(a,b);
        p[b] = a;
        if (r[a] == r[b]) r[a]++;
        return true;
    }
};

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

    int N;
    cin >> N;
    vector<int> P(N);
    for (int i = 0; i < N; i++) cin >> P[i];

    sort(P.begin(), P.end());

    unordered_map<int, int> pos;
    for (int i = 0; i < N; i++) pos[P[i]] = i;

    DSU dsu(N);

    int maxP = P.back();
    for (int i = 0; i < N; i++) {
        for (long long m = 2LL * P[i]; m <= maxP; m += P[i]) {
            if (pos.count(m)) {
                dsu.unite(i, pos[m]);
            }
        }
    }

    vector<tuple<int,int,int>> edges;
    for (int i = 0; i + 1 < N; i++) {
        int cost = P[i+1] % P[i];
        edges.emplace_back(cost, i, i+1);
    }

    sort(edges.begin(), edges.end());

    long long ans = 0;
    for (auto &[w,u,v] : edges) {
        if (dsu.unite(u,v)) ans += w;
    }

    cout << ans << "\n";
}

• 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