Submission #582427

#TimeUsernameProblemLanguageResultExecution timeMemory
582427mosiashvililukaSirni (COCI17_sirni)C++14
14 / 140
5084 ms163496 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...