Submission #1326662

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326662		Szil	Sirni (COCI17_sirni)	C++20	14 / 140	5116 ms	851968 KiB

sirni

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

struct dsu {

    vector<int> par, siz;

    dsu(int n) {
        par.resize(n);
        siz.resize(n+1, 1);
        iota(par.begin(), par.end(), 0);
    }

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

    bool unio(int u, int v) {
        u = holvan(u); v = holvan(v);
        if (u == v) return false;
        if (siz[u] > siz[v]) swap(u, v);
        siz[v] += siz[u];
        par[u] = v;
        return true;
    }

};

void solve() {
    int n; cin >> n;
    vector<int> v(n);
    for (int i = 0; i < n; i++) cin >> v[i];

    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    int m = v.size();
    set<array<int, 3>> edges;
    for (int i = 0; i < m; i++) {
        for (int j = v[i]; j <= 10'000'000; j+=v[i]) {
            auto it = lower_bound(v.begin(), v.end(), j);
            if (it != v.end()) {
                edges.insert({(*it)-j, (int)(it-v.begin()), i});
                it++;
                if (it != v.end()) edges.insert({(*it)-j, (int)(it-v.begin()), i});
            } else break;
        }
    }
    ll ans = 0;
    dsu d(m);
    for (auto [w, u, v] : edges) {
        if (d.unio(u, v)) ans += w;
    }
    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int t = 1; 
    // cin >> t;
    while (t--) solve();
    return 0;
}

• Subtask 1: 0 / 14
• Subtask 2: 0 / 14
• Subtask 3: 14 / 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