oj.uz

Submission #490248

# Submission time Handle Problem Language Result Execution time Memory
490248 2021-11-26T15:28:54 Z BeanZ Sirni (COCI17_sirni) C++14
0 / 140
 356 ms 238756 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;
            }
        }
        if (nx[i]) last = i;
    }
    sort(E.begin(), E.end(), cmp);
    for (auto j : E){
        dsu(j.u, j.v, j.c);
    }
    cout << ans;
}
/*
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 101376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

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

Subtask #3
0 / 14.0

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

Subtask #4
0 / 14.0

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

Subtask #5
0 / 14.0

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

Subtask #6
0 / 14.0

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

Subtask #7
0 / 14.0

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

Subtask #8
0 / 14.0

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

Subtask #9
0 / 14.0

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

Subtask #10
0 / 14.0

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