| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 667237 | kirakaminski968 | Sirni (COCI17_sirni) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace __gnu_pbds;
using namespace std;
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(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.find(v[1]) != d.find(v[2])){
d.merge(v[1], v[2]);
ans += v[0];
}
}
cout << ans;
}
int main(){
cin.tie(0); ios::sync_with_stdio(0);
solve();
return 0;
}