Submission #1192115

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192115		_callmelucian	Sirni (COCI17_sirni)	C++17	0 / 140	479 ms	50172 KiB

sirni

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

using ll = long long;
using ld = long double;
using pl = pair<ll,ll>;
using pii = pair<int,int>;
using tpl = tuple<int,int,int>;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

struct DSU {
    vector<int> lab;
    DSU (int sz) : lab(sz + 1, -1) {}

    int get (int u) {
        if (lab[u] < 0) return u;
        return lab[u] = get(lab[u]);
    }

    bool unite (int a, int b) {
        a = get(a), b = get(b);
        if (a == b) return 0;
        if (-lab[a] < -lab[b]) swap(a, b);
        lab[a] += lab[b], lab[b] = a;
        return 1;
    }
};

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    /// read input & refine
    int n; cin >> n;
    vector<int> a(n);
    for (int &u : a) cin >> u;
    sort(all(a)), filter(a), n = a.size();
    int mx = *max_element(all(a));

    /// edge case
    if (a[0] == 1) return cout << 0, 0;

    /// generate potential edges
    vector<tpl> edges;
    for (int i = 0; i < n; i++) {
        for (int mult = a[i + 1] / a[i]; 1LL * a[i] * mult <= mx;) {
            // build edge
            int nxt = lower_bound(all(a), max(a[i] + 1, a[i] * mult)) - a.begin();
            if (nxt < n) edges.emplace_back(a[nxt] - a[i] * mult, i, nxt);

            // transition
            if (nxt + 1 < n) mult = max(mult + 1, a[nxt + 1] / a[i]);
            else break;
        }
    }
    sort(all(edges));

    /// build MST using Kruskal algorithm
    DSU dsu(n); ll ans = 0;
    for (tpl iter : edges) {
        int weight, a, b; tie(weight, a, b) = iter;
        if (dsu.unite(a, b)) ans += weight;
    }
    cout << ans;

    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