Submission #195588

#	Time	Username	Problem	Language	Result	Execution time	Memory
195588		dolphingarlic	Sirni (COCI17_sirni)	C++14	140 / 140	4399 ms	711128 KiB

sirni

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

int a[100001];
vector<pair<int, int>> edges[10000001];

int cmp[100001];
int find(int A) {
    while (A != cmp[A]) cmp[A] = cmp[cmp[A]], A = cmp[A];
    return A;
}
void onion(int A, int B) { cmp[find(A)] = cmp[find(B)]; }

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    set<int> s;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        s.insert(x);
    }
    n = 0;
    for (int i : s) {
        cmp[n] = n;
        a[n++] = i;
    }

    for (int i = 0; i < n; i++) {
        if (i != n - 1) edges[a[i + 1] % a[i]].push_back({i, i + 1});
        int lb = i + 1;
        for (int j = 2 * a[i]; j <= a[n - 1]; j += a[i]) {
            while (a[lb] < j) lb++;
            edges[a[lb] % a[i]].push_back({i, lb});
        }
    }
    
    long long ans = 0;
    for (int i = 0; i < a[n - 1]; i++) {
        for (pair<int, int> j : edges[i]) {
            if (find(j.first) != find(j.second)) {
                ans += i;
                onion(j.first, j.second);
            }
        }
    }
    cout << ans;
    return 0;
}

• 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