Submission #1190882

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190882		vusal	Sirni (COCI17_sirni)	C++20	0 / 140	1059 ms	851968 KiB

sirni

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

#define int long long

const int oo = 1e18;
const int MAXN = 1e3 + 7;
const int MAXH = 1e2 + 4;

vector<int>par(MAXN, -1), sz(MAXN, 1);

int getl(int x)
{
    if(par[x] == -1) return x;
    return par[x] = getl(par[x]);
}

bool unite(int a, int b)
{
    a = getl(a);
    b = getl(b);
    if(a == b) return false;
    if(sz[a] > sz[b]) swap(a, b);
    sz[b] += sz[a];
    par[a] = b;
    return true;
}

void _()
{
    int n;
    cin >> n;

    vector<int>v(n);
    for(int &i : v) cin >> i;

    vector<array<int,3>>q;

    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
            q.push_back({min(v[i] % v[j], v[j] % v[i]), v[i], v[j]});
        }
    }

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

    int sum = 0;

    for(auto [w, u, v] : q)
    {
        if(unite(u, v))
        {
            sum += w;
        }
    }

    cout << sum << endl;
}   

signed main()
{
    int tt = 1;
    // cin >> tt;
    while(tt--) _();
}

• 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