Submission #1026789

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026789		vjudge1	Sirni (COCI17_sirni)	C++17	98 / 140	1085 ms	99896 KiB

sirni

#include <bits/stdc++.h>

using namespace std;

int parent[1000005], sz[1000005];

int Find(int x) {
    if (x==parent[x])
        return x;
    return parent[x]=Find(parent[x]);
}

void Union(int a, int b) {
    a=Find(a), b=Find(b);
    if (a==b) return;
    if (sz[a]<sz[b])
        swap(a,b);
    sz[a]+=sz[b];
    parent[b]=a;
}




int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    int a[n];
    for (int i=0;i<n;i++)
        cin >> a[i];
    vector<pair<int, pair<int,int> > > v;
    if (n<=1000) {
        for (int i=0;i<n;i++) {
            for (int j=i+1;j<n;j++) {
                int dolz=min(a[i]%a[j], a[j]%a[i]);
                v.push_back({dolz, {i,j}});
            }
        }
        for (int i=0;i<n;i++)
            sz[i]=1, parent[i]=i;
    }
    else {
        sort(a, a+n);
        int posl_vred=-1;
        vector<int> vred_bez_povt;
        for (int i=0;i<n;i++)
            if (a[i]!=posl_vred)
                vred_bez_povt.push_back(a[i]), posl_vred=a[i];

        int najg_vred=vred_bez_povt.back();
        for (auto x:vred_bez_povt) {
            for (int j=x;j<=najg_vred;j+=x) {
                if (j==x) {
                    auto sleden=upper_bound(vred_bez_povt.begin(), vred_bez_povt.end(), j);
                    if (sleden==vred_bez_povt.end()) continue;
                    int dist=min((*sleden)%x, x%(*sleden));
                    v.push_back({dist, {x, *sleden}});
                }
                else {
                    auto sleden=lower_bound(vred_bez_povt.begin(), vred_bez_povt.end(), j);
                    if (sleden==vred_bez_povt.end()) continue;
                    int dist=min((*sleden)%x, x%(*sleden));
                    v.push_back({dist, {x, *sleden}});
                }
            }
        }
        for (int i=0;i<=najg_vred;i++)
            sz[i]=1, parent[i]=i;
    }
    sort(v.begin(), v.end());
    int rez=0;
    for (auto [dolz, edge]:v) {
        int a=edge.first, b=edge.second;
        if (Find(a)!=Find(b)) {
            rez+=dolz;
            Union(a, b);
        }
    }
    cout << rez;

    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: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14