Submission #1191423

#TimeUsernameProblemLanguageResultExecution timeMemory
1191423hikari1234Sirni (COCI17_sirni)C++20
140 / 140
1056 ms750964 KiB
#pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #pragma GCC target("avx2") #include<bits/stdc++.h> using namespace std; //#define int long long #define ff first #define ss second int n; int a[100005]; set<int> s; vector<int> cards; int par[100005], sz[100005]; int fin(int x){ if(par[x]==x) return x; return par[x]=fin(par[x]); } bool unite(int x, int y){ x=fin(x), y=fin(y); if(x==y) return 0; if(sz[y]>sz[x]) swap(x,y); sz[x]+=sz[y]; par[y]=x; return 1; } signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cin>>n; sz[0]=1; for(int i=1; i<=n; i++){ cin>>a[i]; s.insert(a[i]); sz[i]=1; par[i]=i; } for(auto &x: s){ cards.push_back(x); } int lim=cards.back(); vector<pair<int,int>> edges[lim+5]; int comp=cards.size(); int idx[lim+5]; memset(idx,-1,sizeof(idx)); for(int i=0; i<cards.size(); i++){ idx[cards[i]]=i; } for(int i=lim; i>=0; i--){ if(idx[i]==-1){ idx[i]=idx[i+1]; } } for(int i=0; i<cards.size()-1; i++){ edges[cards[i+1]%cards[i]].emplace_back(i,i+1); for(int j=cards[i]*2; j<=lim; j+=cards[i]){ edges[cards[idx[j]]%cards[i]].emplace_back(i,idx[j]); } } long long tot=0; for(int i=0; i<=lim; i++){ for(pair<int,int> &j: edges[i]){ if(unite(j.ff,j.ss)){ // cout<<i<<" "<<j.ff<<" "<<j.ss<<endl; tot+=i; comp--; if(comp==1){ cout<<tot<<endl; return 0; } } } } cout<<tot<<endl; }
#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...