Submission #582427

#	Time	Username	Problem	Language	Result	Execution time	Memory
582427		mosiashvililuka	Sirni (COCI17_sirni)	C++14	14 / 140	5084 ms	163496 KiB

sirni

#include<bits/stdc++.h>
using namespace std;
long long pas;
const int N=10000000;
int a,b,c,d,e,i,j,ii,jj,zx,xc,f[100009],msh[100009],zm[100009],cmp,K[100009],C,D,E,KK[100009];
pair <int, int> fx[10000009],fx2[10000009];
vector <pair <int, pair <int, int> > > P;
int fnd(int q){
    if(msh[q]==0) return q; else return msh[q]=fnd(msh[q]);
}
void mrg(int q, int w){
    q=fnd(q);w=fnd(w);
    if(q==w) return;
    pas+=e;cmp--;
    if(zm[q]<zm[w]) swap(q,w);
    msh[w]=q;
    if(zm[q]==zm[w]) zm[q]++;
}
void updfx(int q, int w){
    if(w==N+5) return;
    if(fx[q].first==N+5){
        fx[q].first=w;
    }else{
        if(fx[q].second==N+5){
            if(fnd(fx[q].first)!=fnd(w)) fx[q].second=w;
        }
    }
}
void updfx2(int q, int w){
    if(w==-1) return;
    if(fx2[q].first==-1){
        fx2[q].first=w;
    }else{
        if(fx2[q].second==-1){
            if(fnd(fx2[q].first)!=fnd(w)) fx2[q].second=w;
        }
    }
}
int main(){
    ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>a;map <int, int> ma;
    zx=0;
    for(i=1; i<=a; i++){
        cin>>c;
        if(ma[c]!=-1){
            ma[c]=-1;
            zx++;f[zx]=c;
        }
    }
    a=zx;
    if(a==1){
        cout<<0;
        return 0;
    }

    cmp=a;
    while(cmp>1){
        for(i=0; i<=N+3; i++){
            fx[i]={N+5,N+5};fx2[i]={-1,-1};
            if(i<=a+2){
                K[i]=N+5;KK[i]=0;
            }
        }
        for(i=1; i<=a; i++){
            //c=fnd(i);
            fx[f[i]]={i,N+5};
            for(j=f[i]; j<=N; j+=f[i]){
                fx2[j].second=fx2[j].first;
                fx2[j].first=i;
            }
        }
        for(i=N-1; i>=0; i--){
            /*if(fx[i+1].first!=N+5){
                if(fx[i].first==N+5){
                    fx[i].first=fx[i+1].first;
                }else{
                    if(fx[i].second==N+5){
                        fx[i]
                    }
                }
            }*/
            updfx(i,fx[i+1].first);
            updfx(i,fx[i+1].second);
        }
        for(i=1; i<=N; i++){
            updfx2(i,fx2[i-1].first);
            updfx2(i,fx2[i-1].second);
        }
        i=2;
        //cout<<f[i]<<"    "<<fx2[f[i]].first<<" "<<fx2[f[i]].second<<"\n";
        for(i=1; i<=a; i++){
            C=fnd(i);
            for(j=f[i]; j<=N; j+=f[i]){
                ii=fx[j].first;
                if(ii==N+5) continue;
                D=fnd(ii);
                if(D==C){
                    ii=fx[j].second;
                    if(ii==N+5) continue;
                    D=fnd(ii);
                }
                zx=f[ii]%f[i];
                if(K[C]>zx){
                    K[C]=zx;KK[C]=D;
                }
            }

            for(int ha=1; ha<=1; ha++){
            //
            ii=fx2[f[i]].first;
            if(ii==-1) break;
            D=fnd(ii);
            if(D==C){
                ii=fx2[f[i]].second;
                if(ii==-1) break;
                D=fnd(ii);
            }
            /*cout<<i<<" "<<ii<<"   "<<f[i]<<" "<<f[ii]<<"\n";
            return 0;*/
            zx=f[i]%f[ii];
            if(K[C]>zx){
                K[C]=zx;KK[C]=D;
            }
            //
            }
        }


        /*for(i=1; i<=a; i++){
            cout<<K[i]<<" "<<KK[i]<<"\n";
        }*/
        for(i=1; i<=a; i++){
            if(K[i]==N+5) continue;
            c=i;d=KK[i];e=K[i];
            mrg(c,d);
            //
            K[i]=N+5;
        }
    }
    cout<<pas;
    return 0;
}

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