| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 667239 | kirakaminski968 | Sirni (COCI17_sirni) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef vector<int> vi;
const int N = 1e5+100;
struct DSU {
vi e; void init(int N) { e = vi(N,-1); }
int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }
bool sameSet(int a, int b) { return get(a) == get(b); }
int size(int x) { return -e[get(x)]; }
bool unite(int x, int y) { // union by size
x = get(x), y = get(y); if (x == y) return 0;
if (e[x] > e[y]) swap(x,y);
e[x] += e[y]; e[y] = x; return 1;
}
};
int n;
vector<int> v(N), a;
vector<bool> is(N);
vector<array<int, 3>> edges[N];
void solve(){
cin >> n;
a.resize(n);
for(int i = 0; i < n; ++i) cin >> a[i];
DSU d;
d.init(n);
sort(a.begin(),a.end());
a.resize(unique(a.begin(),a.end()) - a.begin());
n = a.size();
for(int i = 0; i < n - 1; ++i){
for(int j = a[i]; j <= a.back(); j += a[i]){
int k = lower_bound(a.begin() + i + 1, a.end(), j) - a.begin();
if(k >= n || a[k] - j > a[i]) continue;
edges[a[k] - j].pb({a[k] - j, k, i});
}
}
ll ans = 0;
for(int i = 0; i < N; ++i)
for(auto v: edges[i]){
if(d.unite(v[1],v[2])){
ans += v[0];
}
}
cout << ans;
}
int main(){
cin.tie(0); ios::sync_with_stdio(0);
solve();
return 0;
}