Submission #1052354

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052354		vjudge1	Sirni (COCI17_sirni)	C++17	0 / 140	484 ms	786432 KiB

sirni

#include <bits/stdc++.h>

using namespace std;


typedef tuple<int,int,int> tiii;

vector<int> nums;

typedef vector<int> vi;
class UnionFind {
private:
    vi p,rank;
public:
    UnionFind(int n) {
        p.assign(n,0); for (int i = 0; i < n; i++) p[i] = i;
        rank.assign(n,0);
    }

    int findSet(int i) {
        return (p[i] == i) ? i : (p[i] == findSet(p[i]));
    }

    bool isSameSet(int i, int j) {
        return (findSet(i) == findSet(j));
    }

    void unionSet(int i, int j) {
    int x = findSet(i), y = findSet(j);
    if (x == y) return;

    if (rank[x] > rank[y]) swap(x,y);
    p[x] = y;
    if (rank[x] == rank[y]) ++rank[y];
}


};




int main()
{

    int n; cin >> n;
    for (int i = 0; i< n; i++) {
        int a; cin >> a;
        nums.push_back(a);
    }
    vector<tiii> EL;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i == j) continue;
            int minimo = min(nums[i]%nums[j], nums[j]%nums[i]);
            EL.push_back({minimo, i, j});
        }
    }
    sort(EL.begin(), EL.end());

    long int mst_cost = 0, num_taken = 0;
    UnionFind UF(n);

    for (auto &[w, u, v] : EL) {
    if (UF.isSameSet(u,v)) continue;
    mst_cost += w;
    UF.unionSet(u,v);
    ++num_taken;
    if(num_taken == n-1) break;
    }
    cout << mst_cost << '\n';


    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