oj.uz

Submission #248063

# Submission time Handle Problem Language Result Execution time Memory
248063 2020-07-12T07:49:22 Z NONAME Sirni (COCI17_sirni) C++14
42 / 140
 935 ms 786436 KB 
#include <bits/stdc++.h>
#define dbg(x) cerr << #x << " = " << x << "\n"
#define fast_io ios_base::sync_with_stdio(0); cin.tie(0); cout.tie()
using namespace std;
using ll = long long;

const int N = int(1e5) + 10;

int n, a[N], pr[N];
ll ans;
vector <pair <ll, pair <int, int> > > v;

int f(int x) { return (x == pr[x]) ? x : pr[x] = f(pr[x]); }

int main() {
    fast_io;

    cin >> n;
    for (int i = 0; i < n; ++i)
        cin >> a[i], pr[i] = i;

    for (int i = 0; i < n; ++i)
    for (int j = i + 1; j < n; ++j)
        v.push_back(make_pair(min(a[i] % a[j], a[j] % a[i]), make_pair(i, j)));

    sort(v.begin(), v.end());
    for (int i = 0; i < int(v.size()); ++i) {
        int x = v[i].second.first, y = v[i].second.second;
        x = f(x);
        y = f(y);

        if (x == y)
            continue;

        ans += v[i].first;
        pr[y] = x;
    }

    cout << ans << "\n";
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 8688 KB Output is correct
2 Correct 72 ms 8688 KB Output is correct
3 Correct 77 ms 8688 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 8688 KB Output is correct
2 Correct 81 ms 8688 KB Output is correct
3 Correct 66 ms 8688 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 8688 KB Output is correct
2 Correct 55 ms 8688 KB Output is correct
3 Correct 66 ms 8688 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 934 ms 786436 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 918 ms 786436 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 935 ms 786436 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 928 ms 786436 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 927 ms 786436 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 924 ms 786436 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 919 ms 786436 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -