제출 #1337171

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

sirni

#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
int par[10001000];
int nxt[10001000];
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;
}
vector<pair<int,int>> edges[5000100];
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)
        nxt[i]=i;
    for(int i=1e7;i;i--)
        if(!nxt[i])nxt[i]=nxt[i+1];
    for(auto i:st) {
        x=nxt[i+1];
        while(x) {
            edges[x%i].push_back({x,i});
            int z = x/i;
            x=nxt[(z+1)*i];
        }
    }
    long long cost=0;
    for(int i=0;i<5e6;i++)
        for(auto[u,v]:edges[i])
            if(merge(u,v))
                cost+=i;
    cout<<cost;
}

• 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