oj.uz

Submission #1016627

# Submission time Handle Problem Language Result Execution time Memory
1016627 2024-07-08T09:27:45 Z daoda Sirni (COCI17_sirni) C++17
Compilation error
 0 ms 0 KB 
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>

#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define FOR(x, a, b) for(int x=a;x < int(b); x++)
#define endl '\n'
#define TESTCASE ll t; cin >> t; for(ll T=0; T < t; T++)

using namespace std;
// using namespace __gnu_pbds;

typedef unsigned long long int ull;
typedef long long int ll;
typedef vector<ll> vll;
typedef pair<ll,ll> pll;
typedef vector<pll> vpll;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<int> vi;
typedef pair<int, int> pi;
typedef vector<pi> vpi;
typedef vector<short> vs;
typedef long double ld;

// template <class T>
// using Tree = 
    // tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const ll INF = ll(1e18) + 10;
const ll INIT = 7;
const ll MAX_VAL = 5000;
const ll MAX_SZ = (ll) 1e4;
const ll MAX_N = 1e5;
const ll MAX_P = 1e7;
const long double eps = 1e-4;
const ll MOD = ll(1e9) + 7;

vi rd = {0, 1, 0, -1}, cd = {1, 0, -1, 0};

ll add(ll a, ll b) {
    return ((a % MOD) + (b % MOD) + 2ll * MOD) % MOD;
}

ll mult(ll a, ll b) {
    return (((a % MOD) * (b % MOD)) + MOD) % MOD;
}

ll lcm(ll a, ll b) {
    return (a * b) / gcd(a, b);
}

struct DSU {
    vi ids, comp_sz;

    DSU(int sz) {
        ids.resize(sz + 1);
        comp_sz.resize(sz + 1, 1);

        FOR(ind, 1, sz + 1) ids[ind] = ind;
    }

    int get(int x) { return ((x == ids[x]) ? x : (ids[x] = get(ids[x]))); }
    int f_sz(int x) { return comp_sz[get(x)]; }
    bool unite(int a, int b) {
        int id_sm = get(a), id_lg = get(b);

        if(id_sm == id_lg) return false;

        if(comp_sz[id_sm] > comp_sz[id_lg]) swap(id_sm, id_lg);

        comp_sz[id_lg] += comp_sz[id_sm];
        ids[id_sm] = id_lg;

        return true;
    }

};

DSU dsu(MAX_N + 1);
vi edge[(MAX_P / 2) + 1];
int closest[MAX_P + 2], dist[MAX_P + 2];

int main() { 

    // freopen(".in", "r", stdin);
    // freopen(".out", "w", stdout);

    fast

    // TESTCASE {
        
    // }

    int n;
    cin >> n;

    int unused_id = 1;

    FOR(i, 0, n) {
        int num;
        cin >> num;

        closest[num] = unused_id;
        unused_id++;
    }

    if(closest[1]) {
        cout << 0;
        return 0;
    }

    for(int i = MAX_P - 1, cur_dist = 1; i >= 1; i--, cur_dist++) {
        if(closest[i]) cur_dist = 0;

        closest[i] = closest[i + cur_dist];
        dist[i] = cur_dist;
    }

    FOR(i, 2, MAX_P + 1) {
        if(closest[i] && !dist[i]) {
            if(closest[i + 1]) edge[dist[i + 1] + 1].push_back(make_pair(closest[i + 1], closest[i]));

            for(int j = 2*i; j <= MAX_P; j += i) {
                if(!closest[j]) break;
                edge[dist[j]].push_back(make_pair(closest[j], closest[i]));
            }
        }
    }

    ll ans = 0;

    FOR(i, 0, MAX_P + 1) {
        for(auto [a, b] : edge[i]) {
            if(dsu.unite(a, b)) ans += i;
            // cout << a << " " << b << " " << i << endl;
        }
    }

    cout << ans;
}

Compilation message

sirni.cpp: In function 'int main()':
sirni.cpp:121:101: error: no matching function for call to 'std::vector<int>::push_back(std::pair<int, int>)'
  121 |             if(closest[i + 1]) edge[dist[i + 1] + 1].push_back(make_pair(closest[i + 1], closest[i]));
      |                                                                                                     ^
In file included from /usr/include/c++/10/vector:67,
                 from /usr/include/c++/10/functional:62,
                 from /usr/include/c++/10/pstl/glue_algorithm_defs.h:13,
                 from /usr/include/c++/10/algorithm:74,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from sirni.cpp:1:
/usr/include/c++/10/bits/stl_vector.h:1187:7: note: candidate: 'void std::vector<_Tp, _Alloc>::push_back(const value_type&) [with _Tp = int; _Alloc = std::allocator<int>; std::vector<_Tp, _Alloc>::value_type = int]'
 1187 |       push_back(const value_type& __x)
      |       ^~~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:1187:35: note:   no known conversion for argument 1 from 'std::pair<int, int>' to 'const value_type&' {aka 'const int&'}
 1187 |       push_back(const value_type& __x)
      |                 ~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_vector.h:1203:7: note: candidate: 'void std::vector<_Tp, _Alloc>::push_back(std::vector<_Tp, _Alloc>::value_type&&) [with _Tp = int; _Alloc = std::allocator<int>; std::vector<_Tp, _Alloc>::value_type = int]'
 1203 |       push_back(value_type&& __x)
      |       ^~~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:1203:30: note:   no known conversion for argument 1 from 'std::pair<int, int>' to 'std::vector<int>::value_type&&' {aka 'int&&'}
 1203 |       push_back(value_type&& __x)
      |                 ~~~~~~~~~~~~~^~~
sirni.cpp:125:74: error: no matching function for call to 'std::vector<int>::push_back(std::pair<int, int>)'
  125 |                 edge[dist[j]].push_back(make_pair(closest[j], closest[i]));
      |                                                                          ^
In file included from /usr/include/c++/10/vector:67,
                 from /usr/include/c++/10/functional:62,
                 from /usr/include/c++/10/pstl/glue_algorithm_defs.h:13,
                 from /usr/include/c++/10/algorithm:74,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from sirni.cpp:1:
/usr/include/c++/10/bits/stl_vector.h:1187:7: note: candidate: 'void std::vector<_Tp, _Alloc>::push_back(const value_type&) [with _Tp = int; _Alloc = std::allocator<int>; std::vector<_Tp, _Alloc>::value_type = int]'
 1187 |       push_back(const value_type& __x)
      |       ^~~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:1187:35: note:   no known conversion for argument 1 from 'std::pair<int, int>' to 'const value_type&' {aka 'const int&'}
 1187 |       push_back(const value_type& __x)
      |                 ~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_vector.h:1203:7: note: candidate: 'void std::vector<_Tp, _Alloc>::push_back(std::vector<_Tp, _Alloc>::value_type&&) [with _Tp = int; _Alloc = std::allocator<int>; std::vector<_Tp, _Alloc>::value_type = int]'
 1203 |       push_back(value_type&& __x)
      |       ^~~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:1203:30: note:   no known conversion for argument 1 from 'std::pair<int, int>' to 'std::vector<int>::value_type&&' {aka 'int&&'}
 1203 |       push_back(value_type&& __x)
      |                 ~~~~~~~~~~~~~^~~
sirni.cpp:133:18: error: cannot decompose non-array non-class type 'int'
  133 |         for(auto [a, b] : edge[i]) {
      |                  ^~~~~~