Submission #1281003

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281003		minhpk	Sirni (COCI17_sirni)	C++20	14 / 140	2939 ms	828084 KiB

sirni

#include <bits/stdc++.h>
using namespace std;
int a;
short mark[10000005];
int nxt[10000005];
struct node{
     int l,r,val;
};
vector<node> v;
bool cmp(node a,node b){
     return a.val<b.val;
}
int par[10000005];
int sz[10000005];
int find(int u){
    if (par[u]==u){
        return u;
    }
    return par[u]=find(par[u]);
}
bool join(int x,int y){
    x=find(x);
    y=find(y);
    if (x==y){
        return false;
    }
    if (sz[x]<sz[y]){
        swap(x,y);
    }
    par[y]=x;
    sz[x]+=sz[y];
    return true;
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> a;
    for (int i=1;i<=a;i++){
         int x;
         cin >> x;
         mark[x]=1;
    }
    nxt[10000001]=-1;
    for (int i=10000000;i>=1;i--){
         if (mark[i]){
             nxt[i]=i;
         }else{
             nxt[i]=nxt[i+1];
         }
    }
    for (int i=1;i<=10000000;i++){
         if (mark[i]){
             int sad=nxt[i+1];
             if(sad!=-1){
                v.push_back({i,sad,sad%i});
             }
             for (int j=i*2;j<=10000000;j+=i){
                  sad=nxt[j];
                  if(sad!=-1){
                      v.push_back({i,sad,sad%i});
                  }else{
                      break;
                  }
             }
         }
    }
    sort(v.begin(),v.end(),cmp);
    for (int i=1;i<=10000000;i++){
         par[i]=i;
         sz[i]=1;
    }
    int res=0;
    for (auto p:v){
         if (join(p.l,p.r)){
             res+=p.val;
         }
    }
    cout << res << "\n";
    return 0;
}

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