#include <bits/stdc++.h>
using namespace std;
int parent[100005], sz[100005];
int Find(int x) {
if (x==parent[x])
return x;
return parent[x]=Find(parent[x]);
}
void Union(int a, int b) {
a=Find(a), b=Find(b);
if (a==b) return;
if (sz[a]<sz[b])
swap(a,b);
sz[a]+=sz[b];
parent[b]=a;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
int a[n];
for (int i=0;i<n;i++)
cin >> a[i];
vector<pair<int, pair<int,int> > > v;
for (int i=0;i<n;i++) {
for (int j=i+1;j<n;j++) {
int dolz=min(a[i]%a[j], a[j]%a[i]);
v.push_back({dolz, {i,j}});
}
}
for (int i=0;i<n;i++)
sz[i]=1, parent[i]=i;
sort(v.begin(), v.end());
int rez=0;
for (auto [dolz, edge]:v) {
int a=edge.first, b=edge.second;
if (Find(a)!=Find(b)) {
rez+=dolz;
Union(a, b);
}
}
cout << rez;
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
39 ms |
8140 KB |
Output is correct |
2 |
Correct |
49 ms |
8140 KB |
Output is correct |
3 |
Correct |
42 ms |
8396 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
51 ms |
7116 KB |
Output is correct |
2 |
Correct |
57 ms |
7116 KB |
Output is correct |
3 |
Correct |
44 ms |
7624 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
44 ms |
6604 KB |
Output is correct |
2 |
Correct |
35 ms |
6860 KB |
Output is correct |
3 |
Correct |
44 ms |
6860 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
573 ms |
786432 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
603 ms |
786432 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
558 ms |
786432 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
610 ms |
786432 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
565 ms |
786432 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
612 ms |
786432 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
593 ms |
786432 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |