#include <bits/stdc++.h>
#define task "ROADS"
#define all(v) (v).begin(), (v).end()
#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
#define Rep(i, r, l) for (int i = (r); i >= (l); --i)
#define DB(X) { cerr << #X << " = " << (X) << '\n'; }
#define DB1(A, _) { cerr << #A << "[" << _ << "] = " << (A[_]) << '\n'; }
#define DB2(A, _, __) { cerr << #A << "[" << _ << "][" << __ << "] = " << (A[_][__]) << '\n'; }
#define DB3(A, _, __, ___) { cerr << #A << "[" << _ << "][" << __ << "][" << ___ << "] = " << (A[_][__][___]) << '\n'; }
#define PR(A, l, r) { cerr << '\n'; rep(_, l, r) DB1(A, _); cerr << '\n';}
#define SZ(x) ((int)(x).size())
#define pb push_back
#define eb emplace_back
#define pf push_front
#define F first
#define S second
#define by(x) [](const auto& a, const auto& b) { return a.x < b.x; } // sort(arr, arr + N, by(a));
#define next ___next
#define prev ___prev
#define y1 ___y1
#define left ___left
#define right ___right
#define y0 ___y0
#define div ___div
#define j0 ___j0
#define jn ___jn
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using namespace std;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vl;
template <typename T> inline void read (T &x) {bool b = 0; char c; while (!isdigit (c = getchar()) && c != '-');
if (c == '-') c = getchar(), b = 1; x = c - 48; while (isdigit(c = getchar())) x = (x<<3) + (x<<1) + c - 48; if (b)x=-x;}
template <typename T> inline void wrip(T x) {if (x > 9) wrip(x / 10); putchar(x%10 + 48); }
const int N = 1e5 + 1, NN = 1e7 + 1;
int n, near[NN], id[NN], rt[N], rk[N];
vi com;
vii edge[NN];
int frt(int i) {return rt[i] == i ? i : rt[i] = frt(rt[i]);}
int main()
{
//freopen(task".inp", "r", stdin);
//freopen(task".out", "w", stdout);
ios_base::sync_with_stdio(false); cin.tie(nullptr);
read(n);
rep(i, 1, n)
{
int p;
read(p);
com.eb(p);
}
sort(all(com));
com.erase(unique(all(com)), com.end());
rep(i, 0, SZ(com) - 1) id[com[i]] = i;
for (int v : com) near[v] = v;
Rep(i, com.back() - 1, 1) if (!near[i]) near[i] = near[i + 1];
rep(i, 0, SZ(com) - 2)
{
for (int j = com[i]; j <= com.back(); j += com[i])
{
int ne = (j == com[i] ? near[j + 1] : near[j]);
if (ne == 0) break;
if (ne >= com[i] + j) j = ne / com[i] * com[i], ne = near[j];
if (ne - j < com[0]) edge[ne - j].pb({i, id[ne]});
}
}
rep(i, 1, SZ(com) - 1) rt[i] = i;
int cnt = 0, ans = 0;
rep(i, 0, NN - 2) for (const ii &E : edge[i])
{
int x = frt(E.F), y = frt(E.S);
if (x != y)
{
if (rk[x] == rk[y]) rk[x]++;
if (rk[x] < rk[y]) swap(x, y);
rt[y] = x;
cnt++;
ans += i;
if (cnt == SZ(com) - 1)
{
wrip(ans);
return 0;
}
}
}
return 0;
}
Compilation message
sirni.cpp: In function 'void read(T&)':
sirni.cpp:40:1: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
40 | if (c == '-') c = getchar(), b = 1; x = c - 48; while (isdigit(c = getchar())) x = (x<<3) + (x<<1) + c - 48; if (b)x=-x;}
| ^~
sirni.cpp:40:37: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
40 | if (c == '-') c = getchar(), b = 1; x = c - 48; while (isdigit(c = getchar())) x = (x<<3) + (x<<1) + c - 48; if (b)x=-x;}
| ^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
215 ms |
278124 KB |
Output is correct |
| 2 |
Correct |
260 ms |
278000 KB |
Output is correct |
| 3 |
Correct |
210 ms |
278124 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
155 ms |
235372 KB |
Output is correct |
| 2 |
Correct |
205 ms |
274796 KB |
Output is correct |
| 3 |
Correct |
208 ms |
278252 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
219 ms |
278328 KB |
Output is correct |
| 2 |
Correct |
206 ms |
276832 KB |
Output is correct |
| 3 |
Correct |
208 ms |
278380 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
220 ms |
251224 KB |
Output is correct |
| 2 |
Correct |
291 ms |
259540 KB |
Output is correct |
| 3 |
Correct |
200 ms |
247652 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
166 ms |
243948 KB |
Output is correct |
| 2 |
Correct |
242 ms |
254956 KB |
Output is correct |
| 3 |
Correct |
205 ms |
247516 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
306 ms |
259764 KB |
Output is correct |
| 2 |
Correct |
264 ms |
256556 KB |
Output is correct |
| 3 |
Correct |
206 ms |
248420 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
172 ms |
239648 KB |
Output is correct |
| 2 |
Correct |
261 ms |
254668 KB |
Output is correct |
| 3 |
Correct |
199 ms |
247908 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
331 ms |
322816 KB |
Output is correct |
| 2 |
Correct |
789 ms |
322444 KB |
Output is correct |
| 3 |
Correct |
363 ms |
324852 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
285 ms |
318444 KB |
Output is correct |
| 2 |
Correct |
1060 ms |
325996 KB |
Output is correct |
| 3 |
Correct |
282 ms |
316316 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
260 ms |
310764 KB |
Output is correct |
| 2 |
Correct |
1362 ms |
361496 KB |
Output is correct |
| 3 |
Correct |
204 ms |
247144 KB |
Output is correct |
