Submission #701014

#TimeUsernameProblemLanguageResultExecution timeMemory
701014aminSirni (COCI17_sirni)C++14
112 / 140
1104 ms786432 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define rep(i,a,b) for(i=a;i<b;i++) ll nex[20000002]; ll sz[20000002],vis[20000002]; ll p[20000000]; ll ans=0; int par(int x) { if(p[x]==x) return x; p[x]=par(p[x]); return p[x]; } void un(int x,int y,ll cost) { //cout<<x<<' '<<y<<' '<<cost<<endl; x=par(x); y=par(y); if(x==y) { return ; } ans+=cost; if(sz[x]<sz[y]) { swap(x,y); } sz[x]+=sz[y]; sz[y]=0; p[y]=x; } int main() { int n; cin>>n; ll a[n]; for(int i=0;i<n;i++) { cin>>a[i]; p[a[i]]=a[i]; sz[a[i]]=1; nex[a[i]]=a[i]; } for(int i=10000002;i>=0;i--) { if(nex[i]==i) { continue; } nex[i]=nex[i+1]; } vector<pair<ll,ll> >v[10000002]; for(int i=1;i<=1e7;i++) { if(nex[i]==i&&vis[i]==0) { vis[i]=1; for(int y=i;y<=1e7;y+=i) { vis[y]=1; // if(nex[y]!=0) if(nex[y]==y) { v[0].push_back({i,y}); } if(nex[y+1]!=0) v[nex[y+1]%i].push_back({i,nex[y+1]}); } } } for(ll i=0;i<1e7;i++) { for(auto y:v[i]) { un(y.first,y.second,i); } } cout<<ans; }
#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...