제출 #1326668

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1326668		Szil	Sirni (COCI17_sirni)	C++20	112 / 140	2925 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;
    }

};

vector<pair<int, int>> buckets[10'000'001];

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()) {
                buckets[(*it)-j].emplace_back((int)(it-v.begin()), i);
                it++;
                if (it != v.end()) buckets[(*it)-j].emplace_back((int)(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: 14 / 14
• Subtask 2: 0 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 14 / 14
• Subtask 8: 14 / 14
• Subtask 9: 0 / 14
• Subtask 10: 14 / 14