제출 #1095446

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1095446		tinnhiemnn	Sirni (COCI17_sirni)	C++17	140 / 140	3341 ms	719804 KiB

sirni

#include <bits/stdc++.h>
using namespace std;
#define file "file"
#define pii pair<int, int>
#define pll pair<long long, long long>
#define pb push_back
#define mp make_pair
const int N=1e5+2, INF=1e7+2;
int n,pa[N],d;
pii a[N];
long long res;
vector<pii> edge[INF];

int findpa(int u)
{
    return pa[u]==u ? u : pa[u]=findpa(pa[u]);
}
bool uni(int u, int v)
{
    u=findpa(u); v=findpa(v);
    if (u==v) return 0;
    pa[v]=u; return 1;
}
int main()
{
    //freopen(file".inp", "r", stdin);
    //freopen(file".out", "w", stdout);
    ios_base::sync_with_stdio(0); cin.tie(0);

    cin>>n;
    for (int i=1;i<=n;i++) {cin>>a[i].first; a[i].second = i;}
    sort(a+1, a+n+1);

    for (int i=1;i<=n;i++) pa[i]=i;

    for (int i=1;i<=n;i++)
    {
        int j=i+1;
        for (int k=a[i].first; k<=INF && j<=n; k+=a[i].first)
        {
            while (j<=n && a[j].first < k) j++;
            if (j<=n) {edge[a[j].first % a[i].first].pb({a[i].second, a[j].second}); j++;}
        }
    }

    for (int x=0;x<=INF;x++)
        for (pii p : edge[x])
    {
        if (uni(p.first, p.second)) {res+=x; d++;}
        if (d == n-1) {cout<<res; return 0;}
    }



}

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 14 / 14
• Subtask 8: 14 / 14
• Subtask 9: 14 / 14
• Subtask 10: 14 / 14