# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
757059 |
2023-06-12T13:29:52 Z |
nonono |
Sirni (COCI17_sirni) |
C++14 |
|
3571 ms |
574264 KB |
#include <bits/stdc++.h>
using namespace std;
struct DSU {
int cnt;
int size;
vector<int> e;
DSU (int _) : size (_) {
e = vector<int> (size, -1);
}
int root(int x) {
return (e[x] < 0 ? x : (e[x] = root(e[x])));
}
bool same(int x, int y) {
return root(x) == root(y);
}
void unite(int x, int y) {
if (same(x, y)) return;
x = root(x), y = root(y);
if (-e[x] > -e[y]) {
swap(x, y);
}
e[y] += e[x];
e[x] = y;
cnt --;
}
};
const int N = (int)1e5;
const int Mx = (int)1e7;
int n;
int a[N];
int nxt[Mx + 1];
vector<pair<int, int>> edges[Mx + 1];
void solve() {
cin >> n;
for (int i = 0; i < n;i ++) {
cin >> a[i];
}
sort(a, a + n);
int ptr = 1;
for (int i = 1; i < n;i ++) {
if (a[i] != a[i - 1]) {
a[ptr] = a[i];
ptr ++;
}
}
n = ptr;
for (int i = 0; i < n; i ++) {
nxt[a[i]] = -(i + 1);
}
for (int i = a[n - 1] - 1; i >= 0; i --) {
if (nxt[i] == 0) {
nxt[i] = nxt[i + 1];
if (nxt[i] < 0) nxt[i] *= -1;
}
}
for (int i = 0; i < n - 1; i ++) {
for (int j = a[i]; j <= a[n - 1]; j += a[i]) {
int nt;
if (j == a[i]) {
nt = (nxt[a[i] + 1] < 0 ? -nxt[a[i] + 1] : nxt[a[i] + 1]);
} else {
nt = (nxt[j] < 0 ? -nxt[j] : nxt[j]);
}
if (a[nt - 1] >= j + a[i]) continue;
edges[a[nt - 1] - j].push_back(make_pair(i + 1, nt));
}
}
int64_t ans = 0;
DSU d(n);
for (int i = 0; i < a[n - 1]; i ++) {
for (auto& e : edges[i]) {
if (!d.same(e.first - 1, e.second - 1)) {
d.unite(e.first - 1, e.second - 1);
ans += i;
}
}
}
cout << ans << '\n';
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
214 ms |
274360 KB |
Output is correct |
2 |
Correct |
225 ms |
276760 KB |
Output is correct |
3 |
Correct |
193 ms |
274384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
115 ms |
235232 KB |
Output is correct |
2 |
Correct |
485 ms |
274884 KB |
Output is correct |
3 |
Correct |
181 ms |
274500 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
181 ms |
274412 KB |
Output is correct |
2 |
Correct |
200 ms |
274224 KB |
Output is correct |
3 |
Correct |
181 ms |
274468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
176 ms |
248916 KB |
Output is correct |
2 |
Correct |
281 ms |
276200 KB |
Output is correct |
3 |
Correct |
191 ms |
254140 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
125 ms |
240736 KB |
Output is correct |
2 |
Correct |
229 ms |
261228 KB |
Output is correct |
3 |
Correct |
161 ms |
247024 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
272 ms |
261196 KB |
Output is correct |
2 |
Correct |
316 ms |
290812 KB |
Output is correct |
3 |
Correct |
191 ms |
252736 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
129 ms |
239440 KB |
Output is correct |
2 |
Correct |
384 ms |
285612 KB |
Output is correct |
3 |
Correct |
173 ms |
251952 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
304 ms |
286944 KB |
Output is correct |
2 |
Correct |
1480 ms |
483572 KB |
Output is correct |
3 |
Correct |
333 ms |
290220 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
283 ms |
286776 KB |
Output is correct |
2 |
Correct |
3029 ms |
574264 KB |
Output is correct |
3 |
Correct |
364 ms |
293988 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
291 ms |
276656 KB |
Output is correct |
2 |
Correct |
3571 ms |
570012 KB |
Output is correct |
3 |
Correct |
191 ms |
254472 KB |
Output is correct |