제출 #1167409

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1167409		warrenn	Sirni (COCI17_sirni)	C++20	140 / 140	1504 ms	784640 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,int> >edges[maxn];

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

컴파일 시 표준 에러 (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: 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