#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define ii pair<int, int>
int pa[100000], sz[100000];
int findSet(int x) {
return pa[x] == x ? x : pa[x] = findSet(pa[x]);
}
void unite(int a, int b) {
a = findSet(a); b = findSet(b);
if (sz[a] > sz[b]) swap(a, b);
pa[a] = b;
sz[b] += sz[a];
}
int main() {
cin.tie(0); ios_base::sync_with_stdio(false);
int n; cin >> n;
set<int> nums;
for (int i = 0; i < n; i++) {
int p; cin >> p;
nums.insert(p);
}
map<int, int> idx;
int ctr = 0;
for (int num : nums) {
idx[num] = ctr++;
}
for (int i = 0; i < ctr; i++) {
sz[i] = 1;
pa[i] = i;
}
vector<pair<int, ii>> edges;
for (int num : nums) {
for (int i = num; i <= 1e7; i += num) {
auto it = nums.upper_bound(i);
if (it != nums.end()) {
edges.pb(mp((*it) % num, mp(idx[num], idx[*it])));
}
}
}
sort(edges.begin(), edges.end());
ll ans = 0;
for (auto e : edges) {
if (e.s.s >= ctr) continue;
if (findSet(e.s.f) != findSet(e.s.s)) {
ans += e.f;
unite(e.s.f, e.s.s);
}
}
cout << ans << endl;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
3 ms |
640 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
94 ms |
640 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
640 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1143 ms |
34840 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
107 ms |
4972 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2679 ms |
59392 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
484 ms |
10208 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1121 ms |
35400 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1262 ms |
35276 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
103 ms |
5608 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |