#include<bits/stdc++.h>
using namespace std;
const int maxN=(1e5)+5;
const int maxV=(1e7)+5;
const int inf=INT_MAX;
struct tip
{
int x,y,cost;
bool operator<(const tip& other)
{
return cost<other.cost;
}
};
class dsu
{
private:
int t[maxN];
public:
dsu(int n)
{
for(int i=1;i<=n;i++)
t[i]=-1;
}
inline int getRoot(int x)
{
//getting the root
int y=x;
while(t[y]>0) y=t[y];
//road compression
int z=y;
y=x;
while(y!=z)
{
int aux=t[y];
t[y]=z;
y=aux;
}
return y;
}
inline void unite(int x,int y)
{
int tx=getRoot(x);
int ty=getRoot(y);
if(tx<ty)
{
t[tx]+=t[ty];
t[ty]=tx;
}
else
{
t[ty]+=t[tx];
t[tx]=ty;
}
}
};
vector<tip> edges;
vector<pair<int,int> > e[maxV];
int n,v[maxN],cnt,M[maxV],nrm[maxN],x,y,cst,tx,ty;
long long sol;
inline int cost(int x,int y)
{
int xa,ya;
xa=M[x];
ya=M[y];
return min((xa%ya),(ya%xa));
}
int taken=0;
int main()
{
// freopen("sirni.in","r",stdin);
// freopen("sirni.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&v[i]);
sort(v+1,v+n+1);
v[n+1]=inf;
for(int i=1;i<=n;i++)
{
if(i==1 || v[i]!=v[i-1]) cnt++;
M[cnt]=v[i];
nrm[i]=cnt;
}
for(int i=1;i<=cnt;i++)
{
int x=M[i];
if(x>=v[n]) continue;
int ind=upper_bound(v+1,v+n+1,x)-v;
e[cost(i,nrm[ind])].push_back({i,nrm[ind]});
int lst=nrm[ind];
for(int j=x+x;j<=v[n];j+=x)
{
if(j>v[n]) continue;
ind=lower_bound(v+1,v+n+1,j)-v;
if(nrm[ind]!=lst) e[cost(i,nrm[ind])].push_back({i,nrm[ind]});
lst=nrm[ind];
}
}
for(int i=0;i<=v[n];i++)
for(auto it:e[i])
edges.push_back({it.first,it.second,i});
//for(auto it:edges)
// printf("%d %d% d\n",it.x,it.y,it.cost);
dsu D=dsu(n);
for(auto it:edges)
{
if(taken==cnt-1) break;
x=it.x;
y=it.y;
cst=it.cost;
tx=D.getRoot(x);
ty=D.getRoot(y);
if(tx!=ty)
{
taken++;
sol+=1LL*cst;
D.unite(tx,ty);
}
}
printf("%lld\n",sol);
return 0;
}
Compilation message
sirni.cpp: In function 'int main()':
sirni.cpp:92:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
~~~~~^~~~~~~~~
sirni.cpp:95:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&v[i]);
~~~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
278 ms |
235512 KB |
Output is correct |
| 2 |
Correct |
365 ms |
240816 KB |
Output is correct |
| 3 |
Correct |
248 ms |
235768 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
221 ms |
235508 KB |
Output is correct |
| 2 |
Correct |
1112 ms |
237056 KB |
Output is correct |
| 3 |
Correct |
289 ms |
235868 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
254 ms |
235344 KB |
Output is correct |
| 2 |
Correct |
274 ms |
235292 KB |
Output is correct |
| 3 |
Correct |
251 ms |
235512 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
439 ms |
258404 KB |
Output is correct |
| 2 |
Correct |
942 ms |
323288 KB |
Output is correct |
| 3 |
Correct |
524 ms |
276296 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
249 ms |
240212 KB |
Output is correct |
| 2 |
Correct |
590 ms |
307320 KB |
Output is correct |
| 3 |
Correct |
437 ms |
259552 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
707 ms |
307032 KB |
Output is correct |
| 2 |
Correct |
1188 ms |
386960 KB |
Output is correct |
| 3 |
Correct |
509 ms |
274864 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
290 ms |
245196 KB |
Output is correct |
| 2 |
Correct |
1083 ms |
382912 KB |
Output is correct |
| 3 |
Correct |
502 ms |
274576 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
509 ms |
273008 KB |
Output is correct |
| 2 |
Runtime error |
4147 ms |
786436 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
515 ms |
273552 KB |
Output is correct |
| 2 |
Execution timed out |
5109 ms |
530372 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
298 ms |
241008 KB |
Output is correct |
| 2 |
Execution timed out |
5108 ms |
729544 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
