oj.uz

Submission #490254

# Submission time Handle Problem Language Result Execution time Memory
490254 2021-11-26T15:41:19 Z BeanZ Sirni (COCI17_sirni) C++14
140 / 140
 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

sirni.cpp: In function 'int main()':
sirni.cpp:40:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sirni.cpp:41:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |         freopen("test.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory 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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory 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

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory 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

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory 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

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory 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

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory 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

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory 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

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory 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

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory 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

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory 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