Submission #248069

#	Time	Username	Problem	Language	Result	Execution time	Memory
248069		NONAME	Sirni (COCI17_sirni)	C++14	42 / 140	910 ms	786436 KiB

sirni

#include <bits/stdc++.h>
#define dbg(x) cerr << #x << " = " << x << "\n"
#define fast_io ios_base::sync_with_stdio(0); cin.tie(0); cout.tie()
using namespace std;
using ll = long long;

const int N = int(1e5) + 10;

int n, a[N], pr[N];
ll ans;
vector <pair <ll, pair <int, int> > > v;

int f(int x) { return (x == pr[x]) ? x : pr[x] = f(pr[x]); }

int main() {
    fast_io;

    cin >> n;
    for (int i = 0; i < n; ++i)
        cin >> a[i], pr[i] = i;

    for (int i = 0; i < n; ++i)
    for (int j = i + 1; j < n; ++j)
        v.push_back(make_pair(max(a[i], a[j]) % min(a[i], a[j]), make_pair(i, j)));

    sort(v.begin(), v.end());
    for (int i = 0; i < int(v.size()); ++i) {
        int x = v[i].second.first, y = v[i].second.second;
        x = f(x);
        y = f(y);

        if (x == y)
            continue;

        ans += v[i].first;
        pr[y] = x;
    }

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

• 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