#include <iostream>
#include <algorithm>
#include <vector>
#define DIM 100010
using namespace std;
//ifstream fin ("date.in");
//ofstream fout ("date.out");
struct idk{
int x,y,cost;
};
vector <idk> mch;
int n,i,j,k,last,maxi,nr;
int v[DIM],t[DIM],poz[10000010];
inline int cmp (idk a, idk b){
return a.cost < b.cost;
}
inline int rad (int x){
while (t[x] > 0)
x = t[x];
return x;
}
int main (){
cin>>n;
for (i=1;i<=n;i++){
cin>>v[i];
maxi = max (maxi,v[i]);
}
sort (v+1,v+n+1);
k = 1;
for (i=2;i<=n;i++)
if (v[i] != v[i-1])
v[++k] = v[i];
for (i=1;i<=n;i++)
poz[v[i]] = i;
n = k;
for (i=1;i<=n;i++){
int last = i+1;
if (i < n){
int r = min (v[i]%v[i+1],v[i+1]%v[i]);
mch.push_back({i,i+1,r});
}
for (j=v[i]+v[i];j<=maxi;j+=v[i]){
if (poz[j]){ /// e in sir
if (last != poz[j]){
int r = min (v[i]%j,j%v[i]);
mch.push_back({i,poz[j],r});
last = poz[j];
}
} else {
int st = 1, dr = n, val = j;
while (st <= dr){
int mid = (st+dr)>>1;
if (v[mid] >= val){
dr = mid-1;
nr = mid;
} else st = mid+1;
}
if (last != nr){
int r = min (v[i]%v[nr],v[nr]%v[i]);
mch.push_back({i,nr,r});
last = nr;
}}}}
sort (mch.begin(),mch.end(),cmp);
for (i=1;i<=n;i++)
t[i] = -1;
int sol = 0;
for (int i=0;i<mch.size();i++){
int x = mch[i].x, y = mch[i].y;
int rx = rad(x), ry = rad(y);
if (rx != ry){
sol += mch[i].cost;
if (t[rx] < t[ry]){
t[rx] += t[ry];
t[ry] = rx;
} else {
t[ry] += t[rx];
t[rx] = ry;
}}}
cout<<sol;
return 0;
}
Compilation message
sirni.cpp: In function 'int main()':
sirni.cpp:70:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0;i<mch.size();i++){
~^~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
4216 KB |
Output is correct |
2 |
Correct |
115 ms |
5480 KB |
Output is correct |
3 |
Correct |
18 ms |
4472 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
4 ms |
504 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
4472 KB |
Output is correct |
2 |
Correct |
6 ms |
2808 KB |
Output is correct |
3 |
Correct |
14 ms |
4396 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
296 ms |
17780 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
46 ms |
7656 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
607 ms |
54700 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
93 ms |
7808 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
441 ms |
65432 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
453 ms |
65372 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
89 ms |
37868 KB |
Output is correct |
2 |
Execution timed out |
5127 ms |
426376 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |