Submission #1281004

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281004		minhpk	Sirni (COCI17_sirni)	C++20	140 / 140	1631 ms	609104 KiB

sirni

#include <bits/stdc++.h>
using namespace std;
int a;
short mark[10000005];
int nxt[10000005];
struct node{
     int l,r,val;
};
vector<pair<int,int>> z[5000005];
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){
                z[sad%i].push_back({i,sad});
             }
             for (int j=i*2;j<=10000000;j+=i){
                  sad=nxt[j];
                  if(sad!=-1){
                      z[sad%i].push_back({i,sad});
                  }else{
                      break;
                  }
             }
         }
    }
    for (int i=1;i<=10000000;i++){
         par[i]=i;
         sz[i]=1;
    }
    int res=0;
//    cerr << "ok" << "\n";
    for (int i=0;i<=5000000;i++){
         if (z[i].empty()){
             continue;
         }
//         cerr << i << "\n";
         for (auto p:z[i]){
              if (join(p.first,p.second)){
                  res+=i;
              }
         }
    }
    cout << res << "\n";
    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