# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
1026789 |
2024-07-18T11:06:56 Z |
vjudge1 |
Sirni (COCI17_sirni) |
C++17 |
|
1085 ms |
99896 KB |
#include <bits/stdc++.h>
using namespace std;
int parent[1000005], sz[1000005];
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;
if (n<=1000) {
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;
}
else {
sort(a, a+n);
int posl_vred=-1;
vector<int> vred_bez_povt;
for (int i=0;i<n;i++)
if (a[i]!=posl_vred)
vred_bez_povt.push_back(a[i]), posl_vred=a[i];
int najg_vred=vred_bez_povt.back();
for (auto x:vred_bez_povt) {
for (int j=x;j<=najg_vred;j+=x) {
if (j==x) {
auto sleden=upper_bound(vred_bez_povt.begin(), vred_bez_povt.end(), j);
if (sleden==vred_bez_povt.end()) continue;
int dist=min((*sleden)%x, x%(*sleden));
v.push_back({dist, {x, *sleden}});
}
else {
auto sleden=lower_bound(vred_bez_povt.begin(), vred_bez_povt.end(), j);
if (sleden==vred_bez_povt.end()) continue;
int dist=min((*sleden)%x, x%(*sleden));
v.push_back({dist, {x, *sleden}});
}
}
}
for (int i=0;i<=najg_vred;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;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
51 ms |
8136 KB |
Output is correct |
2 |
Correct |
50 ms |
8104 KB |
Output is correct |
3 |
Correct |
43 ms |
6600 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
51 ms |
6604 KB |
Output is correct |
2 |
Correct |
57 ms |
6604 KB |
Output is correct |
3 |
Correct |
44 ms |
6604 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
44 ms |
6604 KB |
Output is correct |
2 |
Correct |
36 ms |
6604 KB |
Output is correct |
3 |
Correct |
46 ms |
8392 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
220 ms |
26016 KB |
Output is correct |
2 |
Correct |
806 ms |
58376 KB |
Output is correct |
3 |
Correct |
365 ms |
50704 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
34 ms |
10488 KB |
Output is correct |
2 |
Correct |
314 ms |
50096 KB |
Output is correct |
3 |
Correct |
213 ms |
26156 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
446 ms |
51640 KB |
Output is correct |
2 |
Correct |
1077 ms |
99872 KB |
Output is correct |
3 |
Correct |
292 ms |
33580 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
67 ms |
6992 KB |
Output is correct |
2 |
Correct |
1085 ms |
99896 KB |
Output is correct |
3 |
Correct |
290 ms |
33196 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
126 ms |
53808 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
128 ms |
66336 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
25 ms |
22028 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |