oj.uz

Submission #1026738

# Submission time Handle Problem Language Result Execution time Memory
1026738 2024-07-18T10:06:36 Z vjudge1 Sirni (COCI17_sirni) C++17
42 / 140
 612 ms 786432 KB 
#include <bits/stdc++.h>

using namespace std;

int parent[100005], sz[100005];

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;
    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;
    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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 8140 KB Output is correct
2 Correct 49 ms 8140 KB Output is correct
3 Correct 42 ms 8396 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 7116 KB Output is correct
2 Correct 57 ms 7116 KB Output is correct
3 Correct 44 ms 7624 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 6604 KB Output is correct
2 Correct 35 ms 6860 KB Output is correct
3 Correct 44 ms 6860 KB Output is correct

Subtask #4
0 / 14.0

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

Subtask #5
0 / 14.0

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

Subtask #6
0 / 14.0

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

Subtask #7
0 / 14.0

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

Subtask #8
0 / 14.0

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

Subtask #9
0 / 14.0

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

Subtask #10
0 / 14.0

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