제출 #1191427

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

sirni

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define f first
#define s second
using namespace std;


vector<ll> par, sz;

ll getRep(ll a){
    if (par[a]==-1) return a;
    return par[a]=getRep(par[a]);
}

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

void solve(){
    ll n;
    cin>>n;
    par.assign(n, -1);
    sz.assign(n, 1);
    vector<ll> v(n);
    for (int i=0; i<n; i++){
        cin>>v[i];
    }
    vector<tuple<ll, ll, ll>> edges;
    for (int i=0; i<n; i++){
        for (int j=i+1; j<n; j++){
            ll cost=min(v[i]%v[j], v[j]%v[i]);
            edges.pb({cost, i, j});
        }
    }
    sort(edges.begin(), edges.end());
    ll ans=0;
    for (auto [w, from, to] : edges) {
        if (unite(from, to)) ans += w;
    }
    cout<<ans<<endl;
}

int main()
{
    ll t=1;
    // cin>>t;
    while (t--){
        solve();
    }

    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