Submission #1010855

#	Time	Username	Problem	Language	Result	Execution time	Memory
1010855		overwatch9	Sirni (COCI17_sirni)	C++17	98 / 140	5070 ms	406268 KiB

sirni

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct DSU {
    vector <int> link, sz;
    DSU (int s) {
        link = sz = vector <int> (s+1);
        for (int i = 0; i <= s; i++) {
            link[i] = i;
            sz[i] = 1;
        }
    }
    int head(int x) {
        if (x == link[x])
            return x;
        return link[x] = head(link[x]);
    }
    bool same(int a, int b) {
        return head(a) == head(b);
    }
    void unite(int a, int b) {
        a = head(a);
        b = head(b);
        if (sz[a] < sz[b])
            swap(a, b);
        sz[a] += b;
        link[b] = a;
    }
};
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    vector <int> nums(n);
    for (int i = 0; i < n; i++)
        cin >> nums[i];
    sort(nums.begin(), nums.end());
    DSU dsu(n+1);
    if (n <= 1000) {
        vector <array <int, 3>> mods;
        for (int i = 0; i < n; i++) {
            for (int j = i+1; j < n; j++) {
                int cost = min(nums[i] % nums[j], nums[j] % nums[i]);
                mods.push_back({cost, i, j});
            }
        }
        sort(mods.begin(), mods.end());
        ll ans = 0;
        int sz = mods.size();
        int cnt = 0;
        for (int i = 0; i < sz && cnt < n-1; i++) {
            if (!dsu.same(mods[i][1], mods[i][2])) {
                ans += mods[i][0];
                dsu.unite(mods[i][1], mods[i][2]);
                cnt++;
            }
        }
        cout << ans << '\n';
    } else {
        multiset <pair <int, int>> nums2;
        unordered_map <int, int> cnt;
        for (int i = 0; i < n; i++) {
            nums2.insert({nums[i], i});
            cnt[nums[i]]++;
        }
        int mx = nums2.rbegin()->first;
        vector <array <int, 3>> costs;
        for (int i = 0; i < n; i++) {
            cnt[nums[i]]--;
            nums2.erase(nums2.find({nums[i], i}));
            if (cnt[nums[i]] >= 1) {
                costs.push_back({0, i, nums2.lower_bound({nums[i], 0})->second});
            } else {
                int lst = 0;
                for (int j = nums[i]; j <= mx; j += nums[i]) {
                    auto it = nums2.lower_bound({j, 0});
                    if (it == nums2.end())
                        break;
                    if (lst != it->first) {
                        costs.push_back({it->first % nums[i], i, it->second});
                        lst = it->first;
                    }
                }
            }
        }
        ll ans = 0;
        int c = 0;
        sort(costs.begin(), costs.end());
        for (auto i : costs) {
            if (!dsu.same(i[1], i[2])) {
                ans += i[0];
                dsu.unite(i[1], i[2]);
                c++;
                if (c == n-1)
                    break;
            }
        }
        cout << ans << '\n';
    }
}

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