oj.uz

Submission #1026780

# Submission time Handle Problem Language Result Execution time Memory
1026780 2024-07-18T11:00:57 Z vjudge1 Sirni (COCI17_sirni) C++17
56 / 140
 1022 ms 786432 KB 
#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];
    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];
    vector<pair<int, pair<int,int> > > v;
    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
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 16600 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2652 KB Output is correct
2 Runtime error 774 ms 786432 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 16728 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 27520 KB Output is correct
2 Correct 772 ms 59052 KB Output is correct
3 Correct 343 ms 52276 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 10748 KB Output is correct
2 Correct 310 ms 52440 KB Output is correct
3 Correct 199 ms 27800 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 459 ms 52592 KB Output is correct
2 Correct 1022 ms 101212 KB Output is correct
3 Correct 284 ms 33076 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 11848 KB Output is correct
2 Correct 945 ms 101924 KB Output is correct
3 Correct 290 ms 33856 KB Output is correct

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 135 ms 51240 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 125 ms 66348 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 23 ms 21772 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -