Submission #1167407

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167407		warrenn	Sirni (COCI17_sirni)	C++20	84 / 140	974 ms	851968 KiB

sirni

#include<bits/stdc++.h>
using namespace std;
#define int long long 
const int maxn=1e7+2;

int dsu[maxn];
int nxt[maxn];
vector<pair<int,pair<int,int> > >edges;

int fin(int a){
    if(dsu[a]==a)return a;
    return dsu[a]=fin(dsu[a]);
}

void merg(int a,int b){
    a=fin(a);
    b=fin(b);
    if(a==b)return;
    dsu[a]=b;
}

signed main(){
    int n;
    cin>>n;
    for(int q=1;q<=maxn;q++){
        dsu[q]=q;
    }
    vector<int>p;
    for(int q=1;q<=n;q++){
        int t;
        cin>>t;
        p.push_back(t);
    }
    sort(p.begin(),p.end());
    p.erase(unique(p.begin(),p.end()),p.end());
    int cur=0;
    for(int q=1;q<=maxn;q++){
        while(cur<p.size() && p[cur]<q)cur++;
        if(cur!=p.size()){
            nxt[q]=p[cur];
        }
        else{
            break;
        }
    }

    for(int q=1;q<p.size();q++){
        edges.push_back({p[q]%p[q-1],{p[q],p[q-1]}});
    }
    for(auto r : p){
        for(int q=r;q<=maxn;q+=r){
            if(nxt[q]!=0){
                edges.push_back({nxt[q]%r,{r,nxt[q]}});
            }
            else break;
        }
    }
    sort(edges.begin(),edges.end());
    int ans=0;
    for(auto r : edges){
        int w=r.first;
        int u=r.second.first;
        int v=r.second.second;
        if(fin(u)!=fin(v)){
            merg(u,v);
            ans+=w;
        }
    }
    cout<<ans<<endl;
}

Compilation message (stderr)

sirni.cpp: In function 'int main()':
sirni.cpp:26:15: warning: iteration 10000001 invokes undefined behavior [-Waggressive-loop-optimizations]
   26 |         dsu[q]=q;
      |         ~~~~~~^~
sirni.cpp:25:18: note: within this loop
   25 |     for(int q=1;q<=maxn;q++){
      |                 ~^~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 0 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 14 / 14
• Subtask 8: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14