#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<ii> edges[(int)1e7+10];
for (int num : nums) {
int prev = -1;
for (int i = num; i <= 1e7; i += num) {
auto it = i == num ? nums.upper_bound(i) : nums.lower_bound(i);
if (it != nums.end()) {
if (prev == *it) continue;
prev = *it;
edges[(*it)%num].pb(mp(idx[num], idx[*it]));
} else {
break;
}
}
/*
for (int num2 : nums) {
if (num < num2)
edges.pb(mp(num2%num, mp(idx[num], idx[num2])));
}
*/
}
ll ans = 0;
for (int c = 0; c <= 1e7; c++) {
for (auto e : edges[c]) {
if (findSet(e.f) != findSet(e.s)) {
ans += c;
unite(e.f, e.s);
}
}
}
cout << ans << endl;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
166 ms |
235512 KB |
Output is correct |
2 |
Correct |
242 ms |
237688 KB |
Output is correct |
3 |
Correct |
170 ms |
235512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
168 ms |
235388 KB |
Output is correct |
2 |
Correct |
834 ms |
235940 KB |
Output is correct |
3 |
Correct |
171 ms |
235536 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
167 ms |
235356 KB |
Output is correct |
2 |
Correct |
168 ms |
235512 KB |
Output is correct |
3 |
Correct |
169 ms |
235512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1022 ms |
254320 KB |
Output is correct |
2 |
Correct |
2877 ms |
280888 KB |
Output is correct |
3 |
Correct |
1062 ms |
257892 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
219 ms |
238200 KB |
Output is correct |
2 |
Correct |
692 ms |
258648 KB |
Output is correct |
3 |
Correct |
875 ms |
252808 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2068 ms |
266580 KB |
Output is correct |
2 |
Correct |
3636 ms |
296184 KB |
Output is correct |
3 |
Correct |
1107 ms |
257500 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
327 ms |
241880 KB |
Output is correct |
2 |
Correct |
2442 ms |
289100 KB |
Output is correct |
3 |
Correct |
1044 ms |
256744 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1102 ms |
257368 KB |
Output is correct |
2 |
Execution timed out |
5084 ms |
348248 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1086 ms |
257028 KB |
Output is correct |
2 |
Execution timed out |
5083 ms |
349400 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
245 ms |
239432 KB |
Output is correct |
2 |
Execution timed out |
5089 ms |
368996 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |