oj.uz

Submission #490250

# Submission time Handle Problem Language Result Execution time Memory
490250 2021-11-26T15:35:56 Z BeanZ Sirni (COCI17_sirni) C++14
98 / 140
 943 ms 786436 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#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("test.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;
}
/*
cbc
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 78 ms 160904 KB Output is correct
2 Correct 135 ms 165248 KB Output is correct
3 Correct 81 ms 161340 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 157372 KB Output is correct
2 Correct 318 ms 159160 KB Output is correct
3 Correct 84 ms 161404 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 161256 KB Output is correct
2 Correct 79 ms 160024 KB Output is correct
3 Correct 79 ms 161416 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 249 ms 215000 KB Output is correct
2 Correct 707 ms 264168 KB Output is correct
3 Correct 314 ms 215004 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 171128 KB Output is correct
2 Correct 451 ms 260696 KB Output is correct
3 Correct 301 ms 210940 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 432 ms 264160 KB Output is correct
2 Correct 798 ms 362728 KB Output is correct
3 Correct 292 ms 214928 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 171252 KB Output is correct
2 Correct 818 ms 362832 KB Output is correct
3 Correct 306 ms 214908 KB Output is correct

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 342 ms 284824 KB Output is correct
2 Runtime error 793 ms 786436 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 347 ms 284900 KB Output is correct
2 Runtime error 841 ms 786436 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 213616 KB Output is correct
2 Runtime error 943 ms 786436 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -