#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 < n; 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])));
}
}
*/
for (int num2 : nums) {
if (num < num2)
edges.pb(mp(num2%num, mp(idx[num], idx[num2])));
}
}
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 |
Correct |
87 ms |
6756 KB |
Output is correct |
2 |
Correct |
87 ms |
6760 KB |
Output is correct |
3 |
Correct |
99 ms |
6760 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
100 ms |
6768 KB |
Output is correct |
2 |
Correct |
55 ms |
3700 KB |
Output is correct |
3 |
Correct |
101 ms |
6760 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
101 ms |
6760 KB |
Output is correct |
2 |
Correct |
80 ms |
6764 KB |
Output is correct |
3 |
Correct |
104 ms |
6752 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
5066 ms |
404480 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
4853 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 |
Execution timed out |
5096 ms |
404324 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
5093 ms |
398148 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
5110 ms |
404844 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
5098 ms |
404736 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
4989 ms |
786436 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |