Submission #1281295

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281295		marcus06	Sirni (COCI17_sirni)	C++20	0 / 140	286 ms	330280 KiB

sirni

#include <bits/stdc++.h>
using namespace std;
using lli = long long;

#ifdef LOCAL
#include </home/marcus06/CP/Library/debug.h>
#else
#define debug(...) 
#endif

/*How to use:
  Tvector <int, 2> g(n); //graph
  Tvector <int, 3> f(n, k, 2) = f[n][k][2]
*/
template <class Tp, int D = 1>
struct Vec : public vector<Vec<Tp, D - 1>> {
    static_assert(D >= 1, "Dimension must be positive");
    template <class... Args>
    Vec(int n = 0, Args... args) : vector<Vec<Tp, D - 1>>(n, Vec<Tp, D - 1>(args...)) {}
};
 
template <class Tp>
struct Vec<Tp, 1> : public vector<Tp> {
    Vec(int n = 0, Tp val = Tp()) : vector<Tp>(n, val) {}
};

struct UnionFind {
    int n;
    vector <int> par;

    UnionFind(int _n): n(_n) {
        par.resize(n);
        iota(par.begin(), par.end(), 0);
    }

    int find(int u) {
        return (u == par[u] ? u : par[u] = find(par[u]));
    }

    bool unite(int u, int v) {
        u = find(u), v = find(v);
        if (u == v) return false;
        par[v] = u;
        return true;
    }
};

void solve() {
    int n;
    cin >> n;

    vector <int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    sort(a.begin(), a.end());

    UnionFind dsu(n);
    for (int i = 0; i + 1 < n; ++i) {
        if (a[i] == a[i + 1]) {
            dsu.unite(i, i + 1);
        }
    }

    int mx = *max_element(a.begin(), a.end());
    vector <int> pos(mx + 1, -1); //any pos because all position with same value is connected
    for (int i = 0; i < n; ++i) {
        pos[a[i]] = i;
    }

    vector <int> R(mx + 1, -1);
    for (int i = 0; i < n; ++i) {
        R[a[i]] = a[i];
    }

    for (int i = mx - 1; i >= 1; --i) {
        if (R[i] == -1) R[i] = R[i + 1];
    }

    Vec <pair <int, int>, 2> store_by_weight(mx + 1);
    for (int i = 1; i <= mx; ++i) {
        if (pos[i] == -1) continue;
        for (int j = 2 * i; j <= mx; j += i) {
            if (R[j] == -1) continue;
            store_by_weight[R[j] % i].emplace_back(pos[i], pos[R[j]]);
        }
    }

    lli ans = 0;
    for (int w = 0; w <= mx; ++w) {
        for (auto [u, v]: store_by_weight[w]) {
            if (dsu.unite(u, v)) ans += w;
        }
    }
    cout << ans << '\n';
}

int main() {
    std::cin.tie(0)->sync_with_stdio(0);
#ifdef LOCAL
    auto begin = std::chrono::high_resolution_clock::now();
#endif

    int tt = 1;
    while (tt--) {
        solve();
    }

#ifdef LOCAL
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    std::cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
#endif
    return 0;
}

• Subtask 1: 0 / 14
• Subtask 2: 0 / 14
• Subtask 3: 0 / 14
• Subtask 4: 0 / 14
• Subtask 5: 0 / 14
• Subtask 6: 0 / 14
• Subtask 7: 0 / 14
• Subtask 8: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14