제출 #1144112

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1144112		tleSquared	Sirni (COCI17_sirni)	C++20	42 / 140	901 ms	851968 KiB

sirni

#include <iostream>
#include <vector>
#include <algorithm>
#define ll long long

using namespace std;

vector<int> parent, ranks;

void make_set(int v) {
    parent[v] = v;
    ranks[v] = 0;
}

int find_set(int v) {
    if (v == parent[v])
        return v;
    return parent[v] = find_set(parent[v]);
}

void union_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b) {
        if (ranks[a] < ranks[b])
            swap(a, b);
        parent[b] = a;
        if (ranks[a] == ranks[b])
            ranks[a]++;
    }
}

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

    vector<pair<ll, pair<ll, ll> > > edges;
    for (int i = 0; i < n; i++)
    {
        for (int j = i+1; j < n; j++)
        {
            edges.push_back(make_pair(min(a[i]%a[j], a[j]%a[i]), make_pair(i, j)));
        }
    }

    int cost = 0;
    parent.resize(n);
    ranks.resize(n);
    for (int i = 0; i < n; i++) make_set(i);

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

    for (pair<ll, pair<ll, ll> > e : edges)
    {
        if (find_set(e.second.first) != find_set(e.second.second))
        {
            cost += e.first;
            // result.push_back(e);
            union_sets(e.second.first, e.second.second);
        }
    }

    cout << cost << endl;

    return 0;
}

• 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