#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include<bits/stdc++.h>
using namespace std;
#define all(v) (v).begin(), (v).end()
#define cst(T) const T&
template<class A, class B> bool umin(A& var, cst(B) val) {
return (val < var) ? (var = val, true) : false;
}
template<class A, class B> bool umax(A& var, cst(B) val) {
return (var < val) ? (var = val, true) : false;
}
typedef long long Int;
typedef long double Real;
const int MOD = 2004010501;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<class X, class Y> Int random(const X& l, const Y& r) {
return uniform_int_distribution<Int>(l,r)(rng);
}
#define DBG(x) cerr << #x << " = " << x << ' ';
#define DBGn(x) cerr << #x << " = " << x << '\n';
const int N = 1e5 + 50;
const int V = 1e7 + 10;
const int INF = 1e9;
int v2pos[V];
class DisjointSet {
private :
int size; int* label = nullptr;
public :
DisjointSet(int size) : size(size) {
if (label != nullptr) delete label;
label = new int[size + 1];
for (int i = 0; i <= size; i++) label[i] = -1;
}
int find_root(int u) {
if (label[u] < 0) return u;
return label[u] = find_root(label[u]);
}
bool merge_set(int u, int v) {
u = find_root(u), v = find_root(v);
if (u == v) return false;
if (-(label[u]) < -(label[v])) swap(u,v);
return label[u] += label[v], label[v] = u, true;
}
bool same_set(int a, int b) {
return find_root(a) == find_root(b);
}
};
struct Edge {
int u,v,w;
bool operator< (cst(Edge) rhs) const {
return w > rhs.w;
}
};
void solve(int testID) {
// DBGn(testID);
int n;
cin >> n;
vector<int> p(n);
for (auto &pi : p) cin >> pi;
sort(all(p));
p.resize(unique(all(p)) - begin(p));
n = int(size(p));
for (int i = 0; i < n; i++) v2pos[p[i]] = i;
priority_queue<Edge> edges;
set<int> values(all(p));
auto find_edges = [&] (int a, int threshold = 0) {
if (!values.empty()) {
int mq = max(0, threshold / a) + 1;
do {
auto it = values.lower_bound(mq * a);
if (it == end(values)) break;
edges.push({a,*it, (*it) % a});
mq = (*it) / a + 1;
} while (1);
}
};
for (auto p_i : p) {
values.erase(p_i);
find_edges(p_i);
}
DisjointSet dsu(n);
Int ans = 0;
while (!edges.empty()) {
auto [u,v,w] = edges.top(); edges.pop();
u = v2pos[u], v = v2pos[v];
if (dsu.merge_set(u,v)) ans += w;
}
cout << ans;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
#define task "WF"
if (fopen(task".inp", "r")) {
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
int numTests = 1;
// cin >> numTests;
for (int i = 1; i <= numTests; i++) solve(i);
}
Compilation message
sirni.cpp: In function 'int main()':
sirni.cpp:112:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
112 | freopen(task".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sirni.cpp:113:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
113 | freopen(task".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
37724 KB |
Output is correct |
| 2 |
Correct |
38 ms |
41428 KB |
Output is correct |
| 3 |
Correct |
7 ms |
37916 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
604 KB |
Output is correct |
| 2 |
Correct |
14 ms |
36444 KB |
Output is correct |
| 3 |
Correct |
6 ms |
37980 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
37724 KB |
Output is correct |
| 2 |
Correct |
4 ms |
29276 KB |
Output is correct |
| 3 |
Correct |
6 ms |
37724 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
296 ms |
24680 KB |
Output is correct |
| 2 |
Correct |
975 ms |
59960 KB |
Output is correct |
| 3 |
Correct |
345 ms |
34740 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
32 ms |
9672 KB |
Output is correct |
| 2 |
Correct |
493 ms |
57288 KB |
Output is correct |
| 3 |
Correct |
256 ms |
21276 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
644 ms |
59764 KB |
Output is correct |
| 2 |
Correct |
1323 ms |
109784 KB |
Output is correct |
| 3 |
Correct |
337 ms |
35032 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
83 ms |
11460 KB |
Output is correct |
| 2 |
Correct |
1380 ms |
108984 KB |
Output is correct |
| 3 |
Correct |
314 ms |
35964 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
403 ms |
71072 KB |
Output is correct |
| 2 |
Execution timed out |
5012 ms |
441008 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
394 ms |
71340 KB |
Output is correct |
| 2 |
Execution timed out |
5031 ms |
439684 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
57 ms |
44492 KB |
Output is correct |
| 2 |
Execution timed out |
5073 ms |
437676 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
