Submission #1146168

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146168		hennessey	Sirni (COCI17_sirni)	C++20	28 / 140	3138 ms	851968 KiB

sirni

#include <bits/stdc++.h>

using namespace std;

#define int long long

vector <int> arr = {};
vector <int> cnt(1e7+2);
vector <int> ind(1e7+2);
vector <vector <int>> di(1e7+2);
vector <int> dsu(100002, -1);
vector <int> siz(100002, 1);

int findroot(int cur) {
    if(dsu[cur] == -1) {
        return cur;
    }
    return dsu[cur] = findroot(dsu[cur]);
}

signed main() {
    //your code goes here
    int n;
    cin >> n;
    vector <int> arr = {};
    for(int i = 0; i < n; i++) {
        int num;
        cin >> num;
        arr.push_back(num);
        cnt[num] = 1;
        ind[num] = i;
    }
    for(int i = 0; i <= 1e7; i++) {
        if(cnt[i] != 1) {
            continue;
        }
        for(int j = (i*2); j <= 1e7; j+=i) {
            di[j].push_back(i);
        }
    }
    sort(arr.begin(), arr.end());
    vector <vector <int>> e = {};
    for(int i = 0; i < n; i++) {
        if(i == 0) {
            continue;
        }
        int v = arr[i];
        int v2 = arr[i-1];
        for(int j = v; j >= v2; j--) {
            int v3 = di[j].size();
            if(v3 > 0) {
                int v4 = v-j;
                for(auto i:di[j]) {
                    e.push_back({i, v, v4});
                }
                // break;
            }
        }
        e.push_back({v2, v, min(v%v2, v2%v)});
    }
    sort(e.begin(), e.end(), [&](auto& left, auto& right) {
        return left[2] < right[2];
    });
    int comp = n;
    int total = 0;
    for(int i = 0; i < e.size(); i++) {
        if(comp == 1) {
            break;
        }
        int v1 = ind[e[i][0]];
        int v2 = ind[e[i][1]];
        int v3 = e[i][2];
        int r1 = findroot(v1);
        int r2 = findroot(v2);
        if(r1 == r2) {
            continue;
        }
        total += v3;
        if(siz[r1] <= siz[r2]) {
            dsu[r1] = r2;
            siz[r2] += r1;
        } else {
            dsu[r2] = r1;
            siz[r1] += r2;
        }
        comp--;
    }
    cout << total << endl;
    return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 0 / 14
• Subtask 3: 14 / 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