This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int mN = 1e5 + 5, mP = 1e7 + 5;
int n, mx, ub[mP], par[mN], sz[mN]; long long ans; vector<int> A; vector<pair<int, int>> edg[mP];
int get(int i){
return (i == par[i]) ? i : par[i] = get(par[i]);
}
void merge(int a, int b, int w){
a = get(a); b = get(b); if (a == b) return;
if (a > b) swap(a, b);
par[a] = b; sz[b] += sz[a]; ans += w;
}
int main(){
cin >> n; A.resize(n);
for (int &i : A) cin >> i;
sort(A.begin(), A.end()); A.erase(unique(A.begin(), A.end()), A.end());
n = A.size(); mx = A.back(); iota(par, par + n, 0); fill(sz, sz + n, 1);
for (int i = 0; i < n; i++) ub[A[i]] = i;
for (int i = mx, cur = n - 1; i >= 0; i--) (ub[i]) ? cur = ub[i] : ub[i] = cur;
for (int i = 0; i < n - 1; i++)
for (int x = A[i]; x <= mx; x += A[i]){
int j = ub[x + (x == A[i])];
if (A[j] < x + A[i])
edg[A[j] % x].push_back({i, j});
}
for (int i = 0; i < mx; i++)
for (auto edge : edg[i])
merge(edge.first, edge.second, i);
cout<<ans<<endl;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |