Submission #1246008

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246008		sakurajima24	Sirni (COCI17_sirni)	C++20	112 / 140	5109 ms	418188 KiB

sirni

#pragma GCC optimize("Ofast,unroll-loops,fast-math,-ffloat-store")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("prefetch-loop-arrays,inline-functions,inline-small-functions,tree-loop-vectorize,tree-slp-vectorize,tree-loop-distribution")
#include <bits/stdc++.h>
using namespace std;
int n,a[100005],b[100005],rnk[100005];
struct DSU{
    vector<int> par;
    void init(int n){
        par.resize(n+5,0);
        for(int i=1; i<=n; i++) par[i]=i;
    }
    int find(int u){
        if(par[u]==u) return u;
        return par[u]=find(par[u]);
    }
    bool join(int u, int v){
        u=find(u);
        v=find(v);
        if(u==v) return 0;
        else{
            if(rnk[u]<rnk[v]) swap(u,v);
            par[v]=u;
            if(rnk[u]==rnk[v]) rnk[u]++;
            return 1;
        }
    }
};
DSU dsu;
struct edge{
    int u,v,w;
};
int cnt=0;
edge e[40000005];
map<int,bool> m;
bool cmp(edge a, edge b){
    return a.w<b.w;
}
main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen(".inp", "r", stdin);
    // freopen(".out", "w", stdout);
    cin>>n;
    for(int i=1; i<=n; i++){
        cin>>b[i];
    }
    sort(b+1, b+1+n);
    int khoibeo=0;
    for(int i=1; i<=n; i++){
        if(!m.count(b[i])){
            a[++khoibeo]=b[i];
            m[b[i]]=1;
        }
    }    
    n=khoibeo;
    for(int i=1; i<=n; i++){
        for(int d=1; a[i]*d<=a[n];){
            int boi=a[i]*d;
            auto it=lower_bound(a+i+1,a+n+1,boi);
            if(it==a+n+1) break;
            int j=it-a;
            int tmp=a[j]/a[i];
            if(tmp<=d) d++;
            else d=tmp;
            e[++cnt].u=i;
            e[cnt].v=j;
            e[cnt].w=(a[j]-boi);
        }
    }
    sort(e+1,e+1+cnt,cmp);
    dsu.init(n);
    long long tong=0;
    for(int i=1; i<=cnt; i++){
        if(!dsu.join(e[i].u,e[i].v)) continue;
        tong+=1LL*e[i].w;
    }
    cout<<tong;
}

Compilation message (stderr)

sirni.cpp:39:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   39 | main(){
      | ^~~~

• 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: 0 / 14
• Subtask 10: 0 / 14