제출 #1337162

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1337162		boyliguanhan	Sirni (COCI17_sirni)	C++17	0 / 140	3563 ms	155576 KiB

sirni

#include<bits/stdc++.h>
using namespace std;
map<int,int>id;
int par[100100];
int abp(int x){
    return par[x]?par[x]=abp(par[x]):x;
}
int merge(int u,int v){
    u=abp(u);
    v=abp(v);
    return u==v?0:par[u]=v;
}
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int n,x,CC=0;
    cin>>n;
    set<int>st;
    while(n--)cin>>x,st.insert(x);
    for(auto i:st)id[i]=++CC;
    set<tuple<int,int,int>> edges;
    for(auto i:st)
        for(int j=i;j<=*--st.end();j+=i)
            edges.insert({*st.lower_bound(j)-j,id[i],id[*st.lower_bound(j)]});
    long long cost=0;
    for(auto[c,u,v]:edges)
        if(merge(u,v))
            cost+=c;
    cout<<cost;
}

• 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