# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
991072 |
2024-06-01T08:20:51 Z |
BF001 |
Sirni (COCI17_sirni) |
C++17 |
|
536 ms |
639052 KB |
#include <bits/stdc++.h>
using namespace std;
#define N 100005
#define se second
#define fi first
int n, par[N];
long long res = 0;
vector<int> p;
struct ii
{
int u, v, w;
bool operator < (ii o){
return w < o.w;
}
};
int find(int u){
if (u == par[u]) return u;
return par[u] = find(par[u]);
}
void unin(int u, int v, int w){
u = find(u);
v = find(v);
if (u == v) return;
par[u] = v;
res += w;
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cin >> n;
for (int i = 1; i <= n; i++){
int val;
cin >> val;
p.push_back(val);
}
sort(p.begin(), p.end());
p.resize(unique(p.begin(), p.end()) - p.begin());
int ma = p.back();
vector<int> near(ma + 1, -1);
vector<vector<pair<int, int>>> eg(ma + 1);
for (int i = 0; i < (int) p.size(); i++){
par[i] = i;
near[p[i]] = i;
}
for (int i = ma - 1; i >= 0; i--){
if (near[i] == -1) near[i] = near[i + 1];
}
for (int i = 0; i < (int) p.size(); i++){
eg[(p[i + 1] - p[i])].push_back({i, i + 1});
for (int j = 2 * p[i]; j <= ma; j += p[i]){
int pos = near[j];
if (pos == -1) continue;
eg[(p[pos] - p[i])].push_back({i, pos});
}
}
for (int i = 0; i <= ma; i++){
for (auto x : eg[i]){
unin(x.fi, x.se, i);
}
}
cout << res;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
231 ms |
555864 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1 ms |
1372 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
247 ms |
556100 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
153 ms |
100820 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
39 ms |
64988 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
393 ms |
137168 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
33 ms |
25056 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
536 ms |
628144 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
505 ms |
639052 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
272 ms |
567124 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |