제출 #1190898

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

sirni

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

#define int long long

const int oo = 1e18;
const int MAXN = 1e5 + 7;

int par[MAXN];
int sz[MAXN];

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]), i, 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()
{
    fill(par, par + MAXN, -1);
    fill(sz, sz + MAXN, 1);
    int tt = 1;
    // cin >> tt;
    while(tt--) _();
}

• 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