Submission #1326673

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326673		Szil	Sirni (COCI17_sirni)	C++20	14 / 140	5122 ms	820096 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;
    }

};

vector<pair<int, int>> buckets[10'000'001];
set<array<int, 3>> hv;

void add(int a, int b, int c) {
    if (hv.count({a, b, c})) return;
    hv.insert({a, b, c});
    buckets[a].emplace_back(b, c);
}

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();
    
    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()) {
                add((*it)-j, (it-v.begin()), i);
                it++;
                if (it != v.end()) add((*it)-j, (it-v.begin()), i);
            } else break;
        }
    }
    ll ans = 0;
    dsu d(m);
    for (int i = 0; i <= 10'000'000; i++) {
        for (auto [u, v] : buckets[i]) {
            if (d.unio(u, v)) ans += i;
        }
    }
    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