#include <iostream>
#include <algorithm>
#include <vector>
#define DIM 100010
using namespace std;
//ifstream cin ("date.in");
//ofstream cout ("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){
int nr = x;
while (t[x] > 0)
x = t[x];
while (t[nr] > 0){
int aux = t[nr];
t[nr] = x;
nr = aux;
}
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];
poz[v[k]] = k;
}
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;
long long 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:76: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 |
4088 KB |
Output is correct |
| 2 |
Correct |
122 ms |
5484 KB |
Output is correct |
| 3 |
Correct |
18 ms |
4472 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
632 KB |
Output is correct |
| 2 |
Correct |
826 ms |
1776 KB |
Output is correct |
| 3 |
Correct |
20 ms |
4536 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
4344 KB |
Output is correct |
| 2 |
Correct |
6 ms |
2808 KB |
Output is correct |
| 3 |
Correct |
14 ms |
4472 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
332 ms |
17076 KB |
Output is correct |
| 2 |
Correct |
938 ms |
54676 KB |
Output is correct |
| 3 |
Correct |
408 ms |
30152 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
44 ms |
7528 KB |
Output is correct |
| 2 |
Correct |
544 ms |
53676 KB |
Output is correct |
| 3 |
Correct |
272 ms |
16076 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
616 ms |
53988 KB |
Output is correct |
| 2 |
Correct |
1234 ms |
103928 KB |
Output is correct |
| 3 |
Correct |
382 ms |
30144 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
92 ms |
7520 KB |
Output is correct |
| 2 |
Correct |
1167 ms |
103884 KB |
Output is correct |
| 3 |
Correct |
412 ms |
30124 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
451 ms |
64648 KB |
Output is correct |
| 2 |
Execution timed out |
5109 ms |
434896 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
457 ms |
64712 KB |
Output is correct |
| 2 |
Execution timed out |
5111 ms |
433856 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
92 ms |
37820 KB |
Output is correct |
| 2 |
Execution timed out |
5114 ms |
425844 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
