| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 490254 | 2021-11-26T15:41:19 Z | BeanZ | Sirni (COCI17_sirni) | C++14 | 4127 ms | 512416 KB |
#include <bits/stdc++.h>
using namespace std;
#define ll int
#define ld long double
#define endl '\n'
const int N = 1e7 + 5;
const int mod = 1e9 + 7;
const int mod2 = 998244353;
const long long lim = 1e7;
const int lg = 18;
const int base = 311;
const int base2 = 511;
const long double eps = 1e-6;
ll ans = 0;
ll p[N], a[N], oke[N], nx[N];
struct viet{
ll u, v, c;
};
bool cmp(viet x, viet y){
return x.c < y.c;
}
ll find_set(ll u){
if (p[u] < 0) return u;
return p[u] = find_set(p[u]);
}
void dsu(ll u, ll v, ll c){
//cout << u << " " << v << " " << c << endl;
u = find_set(u);
v = find_set(v);
if (u == v) return;
if (p[u] > p[v]) swap(u, v);
p[u] += p[v];
p[v] = u;
ans += c;
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
if (fopen("tests.inp", "r")){
freopen("test.inp", "r", stdin);
freopen("test.out", "w", stdout);
}
ll n;
cin >> n;
memset(p, -1, sizeof(p));
for (int i = 1; i <= n; i++){
cin >> a[i];
oke[a[i]] = 1;
}
ll last = 0;
for (int i = lim; i >= 1; i--){
if (oke[i]) last = i;
nx[i] = last;
}
vector<viet> E;
for (int i = 1; i <= lim; i++){
if (oke[i]){
if (nx[i + 1]) E.push_back({i, nx[i + 1], nx[i + 1] - i});
for (int j = i; j <= lim; j += i){
if (nx[j] == 0) break;
if ((j + i) <= nx[j]) continue;
E.push_back({i, nx[j], nx[j] - j});
}
}
}
sort(E.begin(), E.end(), cmp);
for (auto j : E){
dsu(j.u, j.v, j.c);
}
cout << ans;
}
/*
2
10000000
9999999
Ans:
Out:
*/
Compilation message
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 65 ms | 82372 KB | Output is correct |
| 2 | Correct | 103 ms | 83780 KB | Output is correct |
| 3 | Correct | 67 ms | 82696 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 78 ms | 78788 KB | Output is correct |
| 2 | Correct | 274 ms | 79928 KB | Output is correct |
| 3 | Correct | 63 ms | 82756 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 65 ms | 82628 KB | Output is correct |
| 2 | Correct | 67 ms | 81092 KB | Output is correct |
| 3 | Correct | 66 ms | 82756 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 173 ms | 107664 KB | Output is correct |
| 2 | Correct | 412 ms | 132540 KB | Output is correct |
| 3 | Correct | 202 ms | 107952 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 92 ms | 85760 KB | Output is correct |
| 2 | Correct | 301 ms | 131768 KB | Output is correct |
| 3 | Correct | 158 ms | 105992 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 327 ms | 132316 KB | Output is correct |
| 2 | Correct | 517 ms | 181836 KB | Output is correct |
| 3 | Correct | 199 ms | 107928 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 96 ms | 85888 KB | Output is correct |
| 2 | Correct | 568 ms | 181772 KB | Output is correct |
| 3 | Correct | 201 ms | 107924 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 242 ms | 142856 KB | Output is correct |
| 2 | Correct | 2939 ms | 512416 KB | Output is correct |
| 3 | Correct | 310 ms | 143124 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 249 ms | 142808 KB | Output is correct |
| 2 | Correct | 3920 ms | 511348 KB | Output is correct |
| 3 | Correct | 319 ms | 143024 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 97 ms | 115956 KB | Output is correct |
| 2 | Correct | 4127 ms | 504504 KB | Output is correct |
| 3 | Correct | 206 ms | 107992 KB | Output is correct |