Submission #1191350

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191350		oguzhan09	Sirni (COCI17_sirni)	C++20	42 / 140	985 ms	851968 KiB

sirni

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

const int MAXN = 1e5 + 5;

int parent[MAXN];

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

bool unite(int a, int b) {
    int pa = find(a);
    int pb = find(b);
    if (pa == pb) return false;
    parent[pa] = pb;
    return true;
}

int main() {
    int n;
    cin >> n;
    vector<int> p(n);
    for (int i = 0; i < n;i++) cin >> p[i];

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

 
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n;j++) {
            int cost = min(p[i] % p[j], p[j] % p[i]);
            edges.emplace_back(cost, i, j);
        }
    }

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

    for (int i = 0; i < n; ++i) parent[i] = i;

    long long total = 0;
    int count = 0;

    for (auto [cost, u, v] : edges) {
        if (unite(u, v)) {
            total += cost;
            count++;
            if (count == n - 1) break;
        }
    }

    cout << total << endl;
}

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 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