Submission #890155

#TimeUsernameProblemLanguageResultExecution timeMemory
890155asdasdqwerSirni (COCI17_sirni)C++14
140 / 140
1391 ms575156 KiB
#pragma GCC optimize("O3") #pragma GCC target("avx,avx2,sse4") #include <bits/stdc++.h> using namespace std; struct DSU { vector<int32_t> p, r; DSU(int32_t n) { p.assign(n,0); r.assign(n,1); for (int i=0;i<n;i++)p[i]=i; } int get(int32_t i) { if (i != p[i]) p[i]=get(p[i]); return p[i]; } bool unite(int32_t a,int32_t b) { a=get(a); b=get(b); if (a==b)return false; if (r[a]<r[b])swap(a,b); p[b]=a; r[a]+=r[b]; return true; } }; signed test(int n, vector<int> &b) { int lr=b.back(); n=b.size(); vector<int32_t> clos(lr+1,-1); for (int i=0;i<n;i++) { clos[b[i]]=i; } for (int32_t i=lr-1;i>=0;i--) { if (clos[i] == -1) { clos[i]=clos[i+1]; } } typedef array<int32_t,2> pii; vector<vector<pii>> edg(lr+1); for (int i=0;i<n-1;i++) { int x=b[i]; vector<int> tmp; edg[(b[clos[x+1]]%x)].push_back({i, clos[x+1]}); tmp.push_back(clos[x+1]); for (int32_t j=2*x;j<=b.back();j+=x) { if (clos[j] != -1) { if (tmp.back() != clos[j]) { edg[(b[clos[j]]%x)].push_back({clos[j], i}); tmp.push_back(clos[j]); } } } if (tmp.size() == 0 || tmp.back() != n-1) { edg[(b.back()%x)].push_back({n-1, i}); } } DSU d(b.size()); int cost=0; int steps=0; bool term=false; for (int c=0;c<=b.back();c++) { for (auto &x:edg[c]) { if (d.unite(x[0], x[1])) { cost+=c; steps++; if (steps == n-1) { term=true; break; } } } if (term)break; } return cost; } signed main() { ios::sync_with_stdio(false); cin.tie(0); int n;cin>>n; vector<int> a(n); for (int &x:a)cin>>x; if (n == 1) { cout<<0<<"\n"; return 0; } sort(a.begin(),a.end()); vector<int> b; for (int x:a) { if (b.size()==0||b.back()!=x)b.push_back(x); } cout<<test(n,b)<<"\n"; }
#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...