#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define all(aaa) aaa.begin(), aaa.end()
const int N = 1e6 + 5;
int a[N], q[N];
struct E {
int a, b, w;
};
int findSet(int v) {
return q[v] < 0 ? v : q[v] = findSet(q[v]);
}
bool connect(int a, int b) {
a = findSet(a);
b = findSet(b);
if (a == b)
return false;
if (q[a] > q[b])
swap(a, b);
q[a] += q[b];
q[b] = a;
return true;
}
signed main() {
#ifdef HOME
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
fill(q, q + n, -1);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
sort(a, a + n);
vector<E> edges;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
edges.push_back({i, j, a[j] % a[i] });
}
}
sort(all(edges), [](E x, E y) {
return x.w < y.w;
});
ll ans = 0;
for (E e : edges) {
if (connect(e.a, e.b)) {
ans += e.w;
}
}
cout << ans;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
52 ms |
6628 KB |
Output is correct |
2 |
Correct |
51 ms |
6628 KB |
Output is correct |
3 |
Correct |
58 ms |
6624 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
46 ms |
6644 KB |
Output is correct |
2 |
Correct |
44 ms |
6628 KB |
Output is correct |
3 |
Correct |
59 ms |
6756 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
60 ms |
6728 KB |
Output is correct |
2 |
Correct |
46 ms |
6628 KB |
Output is correct |
3 |
Correct |
59 ms |
6624 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1348 ms |
786432 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1330 ms |
786436 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1338 ms |
786436 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1325 ms |
786436 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1336 ms |
786436 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1340 ms |
786436 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1315 ms |
786436 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |