Submission #582431

#TimeUsernameProblemLanguageResultExecution timeMemory
582431mosiashvililukaSirni (COCI17_sirni)C++14
140 / 140
4061 ms585072 KiB
#include<bits/stdc++.h> using namespace std; int a,b,c,d,e,i,j,ii,jj,zx,xc,f[100009],pas,msh[100009],zm[100009],fx[10000009]; //vector <pair <int, pair <int, int> > > P; vector <pair <int, int> > P[10000009]; 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; if(zm[q]<zm[w]) swap(q,w); msh[w]=q; if(zm[q]==zm[w]) zm[q]++; } 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; for(i=1; i<=a; i++){ //cin>>f[i]; fx[f[i]]=i; } for(i=10000000; i>=0; i--){ if(fx[i]==0) fx[i]=fx[i+1]; } for(i=1; i<=a; i++){ for(j=f[i]; j<=10000000; j+=f[i]){ if(j==f[i]) c=fx[j+1]; else c=fx[j]; if(c==0||f[c]-j>=f[i]) continue; zx=(f[c]-j)%f[i]; //P.push_back({zx,{i,c}}); P[zx].push_back({i,c}); } } //sort(P.begin(),P.end()); /*for(ii=0; ii<P.size(); ii++){ e=P[ii].first;c=P[ii].second.first;d=P[ii].second.second; mrg(c,d); }*/ for(i=0; i<=10000000; i++){ for(ii=0; ii<P[i].size(); ii++){ e=i;c=P[i][ii].first;d=P[i][ii].second; mrg(c,d); } } cout<<pas; return 0; }

Compilation message (stderr)

sirni.cpp: In function 'int main()':
sirni.cpp:51:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |         for(ii=0; ii<P[i].size(); ii++){
      |                   ~~^~~~~~~~~~~~
#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...