제출 #972760

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
972760		12345678	Sirni (COCI17_sirni)	C++17	42 / 140	61 ms	8140 KiB

sirni

#include <bits/stdc++.h>

using namespace std;

const int nx=1e3+5;

int n, a[nx], res, cnt, dsu[nx];
vector<tuple<int, int, int>> ed;

int find(int x)
{
    if (dsu[x]==x) return x;
    return dsu[x]=find(dsu[x]);
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n;
    cnt=n;
    for (int i=1; i<=n; i++) cin>>a[i], dsu[i]=i;
    for (int i=1; i<=n; i++) for (int j=i+1; j<=n; j++) ed.push_back({min(a[i]%a[j], a[j]%a[i]), i, j});
    sort(ed.begin(), ed.end());
    for (auto [w, u, v]:ed)
    {
        if (find(u)!=find(v)) res+=w, dsu[find(u)]=find(v), cnt--;
        if (cnt==1) break;
    } 
    cout<<res;
}

• 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