Submission #1266935

#TimeUsernameProblemLanguageResultExecution timeMemory
1266935k12_khoiSirni (COCI17_sirni)C++17
56 / 140
452 ms304852 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long const int N=1e7+5; const int M=25e5+5; struct edges { int X,Y,Z; } b[M]; bool cmp(edges x,edges y) { return x.Z<y.Z; } int n,h,x,y,ma; ll res; int nxt[N],par[N]; bool check[N]; vector <int> a,ve[N]; int acs(int u) { if (par[u]<0) return u; return par[u]=acs(par[u]); } bool join(int u,int v) { int x=acs(u); int y=acs(v); if (x!=y) { if (par[x]>par[y]) swap(x,y); par[x]+=par[y]; par[y]=x; return true; } return false; } int main() { ios_base::sync_with_stdio(NULL); cin.tie(NULL); cout.tie(NULL); cin >> n; a.resize(n); for (int i=0;i<n;i++) cin >> a[i]; sort(a.begin(),a.end()); a.resize(unique(a.begin(),a.end())-a.begin()); n=a.size(); if (a[0]==1) { cout << 0; return 0; } for (int i=1;i<=n;i++) { nxt[a[i-1]]=i; par[i]=-1; } ma=a[n-1]; for (int i=ma;i>=0;i--) if (nxt[i]==0) nxt[i]=nxt[i+1]; for (int i=1;i<n;i++) { x=a[i-1]; y=nxt[x+1]; h++; b[h].X=i; b[h].Y=y; b[h].Z=a[y-1]-x; for (int j=2*x;j<=ma;j+=x) if (y!=nxt[j]) { y=nxt[j]; h++; b[h].X=i; b[h].Y=y; b[h].Z=a[y-1]-j; } else b[h].Z=a[y-1]-j; } sort(b+1,b+h+1,cmp); for (int i=1;i<=h;i++) if (join(b[i].X,b[i].Y)) res+=b[i].Z; cout << res; }
#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...