Submission #1010896

#	Time	Username	Problem	Language	Result	Execution time	Memory
1010896		overwatch9	Sirni (COCI17_sirni)	C++17	140 / 140	955 ms	747792 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;
    }
};
const int maxp = 1e7 + 1;
int nxt[maxp];
vector <array <int, 3>> costs;
vector <pair <int, int>> edges[maxp];
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());
    nums.erase(unique(nums.begin(), nums.end()), nums.end());
    int mx = nums.back();
    fill(nxt, nxt + mx + 1, -1);
    n = nums.size();
    for (int i = 0; i < n; i++)
        nxt[nums[i]] = i;
    for (int i = 0; i < n; i++) {
        for (int j = nums[i]-1; j >= 0 && nxt[j] == -1; j--)
            nxt[j] = nxt[j+1];
    }
    for (int j = mx; j >= nums.back(); j--)
        nxt[j] = n-1;
    for (int i = 0; i < n; i++) {
        if (i+1 < n)
            edges[nums[i+1] % nums[i]].push_back({i, i+1});
        for (int j = nums[i]; j <= mx; j += nums[i]) {
            edges[nums[nxt[j]] % nums[i]].push_back({i, nxt[j]});
        }
    }
    
    ll ans = 0;
    DSU dsu(n+1);
    for (int i = 0, cnt = 0; cnt < n-1 && i <= mx; i++) {
        for (auto j : edges[i]) {
            if (!dsu.same(j.first, j.second)) {
                dsu.unite(j.first, j.second);
                ans += i;
                cnt++;
            }
            if (cnt == 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: 14 / 14
• Subtask 9: 14 / 14
• Subtask 10: 14 / 14