oj.uz

Submission #490222

# Submission time Handle Problem Language Result Execution time Memory
490222 2021-11-26T12:12:16 Z BeanZ Sirni (COCI17_sirni) C++14
0 / 140
 312 ms 238632 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){
    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;
    }
    vector<viet> E;
    ll last = 0;
    for (int i = 1; i <= lim; i++){
        if (nx[i]) last = i;
        if (oke[i]){
            if (last) E.push_back({nx[last], i, i - last});
            for (int j = i; j <= lim; j += i){
                nx[j] = i;
            }
        }
    }
    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:39:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
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.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 60 ms 101252 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 176 ms 157084 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 59 ms 102508 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 209 ms 168668 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 99 ms 165332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 312 ms 168684 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 247 ms 160404 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 139 ms 238568 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 152 ms 238632 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 98 ms 208152 KB Output isn't correct
2 Halted 0 ms 0 KB -