# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
1106945 |
2024-10-31T09:37:23 Z |
vjudge1 |
Sirni (COCI17_sirni) |
C++17 |
|
3066 ms |
452332 KB |
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
const int nmax = 1e7 + 1;
using ll = long long;
int n;
vector<int> v;
int root[nmax + 5];
int nxt[nmax + 5];
struct tt{
int x;
int y;
int z;
};
vector<tt> edge;
bool cmp(tt x, tt y){
return x.z < y.z;
}
int find(int u) { return (u == root[u] ? u : root[u] = find(root[u])); }
signed main(){
cin>>n;
for(int i = 1 , x ; i <= n ; ++i){
cin>>x;
v.push_back(x);
}
sort(v.begin(),v.end());
v.erase(unique(v.begin(),v.end()),v.end());
int j = 0;
for(int i = 1 ; i <= v.back() ; ++i){
while(i > v[j] ) j++;
nxt[i] = v[j];
}
for (int x : v) for (int y = x; y <= v.back(); y += x) {
int p = nxt[(y==x?y+1:y)];
if (!p) break;
if (y + x < p) y = (p - y) / x * x + y;
edge.push_back({x, p, p - y});
}
for(auto i : v) root[i] = i;
sort(edge.begin(),edge.end(),cmp);
ll ans = 0;
for (tt ee : edge) {
int u = ee.x, v = ee.y, c = ee.z;
//cout<<u<<'.'<<v<<'.'<<c<<"\n";
u = find(u), v = find(v);
if (u != v) {
root[u] = v;
ans += 1ll*c;
}
}
cout << ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
78672 KB |
Output is correct |
2 |
Correct |
43 ms |
80928 KB |
Output is correct |
3 |
Correct |
17 ms |
78652 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
4688 KB |
Output is correct |
2 |
Correct |
22 ms |
79364 KB |
Output is correct |
3 |
Correct |
20 ms |
78644 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
78672 KB |
Output is correct |
2 |
Correct |
13 ms |
70272 KB |
Output is correct |
3 |
Correct |
17 ms |
78672 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
110 ms |
23792 KB |
Output is correct |
2 |
Correct |
301 ms |
58644 KB |
Output is correct |
3 |
Correct |
130 ms |
32184 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
13040 KB |
Output is correct |
2 |
Correct |
214 ms |
56620 KB |
Output is correct |
3 |
Correct |
118 ms |
19676 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
216 ms |
56616 KB |
Output is correct |
2 |
Correct |
400 ms |
106020 KB |
Output is correct |
3 |
Correct |
124 ms |
32132 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
37 ms |
13112 KB |
Output is correct |
2 |
Correct |
388 ms |
106008 KB |
Output is correct |
3 |
Correct |
151 ms |
32036 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
155 ms |
93668 KB |
Output is correct |
2 |
Correct |
2079 ms |
436220 KB |
Output is correct |
3 |
Correct |
191 ms |
97748 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
172 ms |
93668 KB |
Output is correct |
2 |
Correct |
2989 ms |
452332 KB |
Output is correct |
3 |
Correct |
216 ms |
103964 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
39 ms |
80896 KB |
Output is correct |
2 |
Correct |
3066 ms |
448240 KB |
Output is correct |
3 |
Correct |
142 ms |
32100 KB |
Output is correct |