oj.uz

Submission #195588

# Submission time Handle Problem Language Result Execution time Memory
195588 2020-01-16T13:36:58 Z dolphingarlic Sirni (COCI17_sirni) C++14
140 / 140
 4399 ms 711128 KB 
#include <bits/stdc++.h>
using namespace std;

int a[100001];
vector<pair<int, int>> edges[10000001];

int cmp[100001];
int find(int A) {
    while (A != cmp[A]) cmp[A] = cmp[cmp[A]], A = cmp[A];
    return A;
}
void onion(int A, int B) { cmp[find(A)] = cmp[find(B)]; }

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    set<int> s;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        s.insert(x);
    }
    n = 0;
    for (int i : s) {
        cmp[n] = n;
        a[n++] = i;
    }

    for (int i = 0; i < n; i++) {
        if (i != n - 1) edges[a[i + 1] % a[i]].push_back({i, i + 1});
        int lb = i + 1;
        for (int j = 2 * a[i]; j <= a[n - 1]; j += a[i]) {
            while (a[lb] < j) lb++;
            edges[a[lb] % a[i]].push_back({i, lb});
        }
    }
    
    long long ans = 0;
    for (int i = 0; i < a[n - 1]; i++) {
        for (pair<int, int> j : edges[i]) {
            if (find(j.first) != find(j.second)) {
                ans += i;
                onion(j.first, j.second);
            }
        }
    }
    cout << ans;
    return 0;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 254 ms 235512 KB Output is correct
2 Correct 359 ms 264824 KB Output is correct
3 Correct 257 ms 235640 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 235384 KB Output is correct
2 Correct 1939 ms 630568 KB Output is correct
3 Correct 242 ms 236152 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 253 ms 235484 KB Output is correct
2 Correct 250 ms 235224 KB Output is correct
3 Correct 241 ms 235552 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1679 ms 249988 KB Output is correct
2 Correct 1677 ms 278024 KB Output is correct
3 Correct 1280 ms 259664 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 237944 KB Output is correct
2 Correct 392 ms 258564 KB Output is correct
3 Correct 1253 ms 249292 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1798 ms 262144 KB Output is correct
2 Correct 1883 ms 296524 KB Output is correct
3 Correct 1659 ms 258860 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 441 ms 240500 KB Output is correct
2 Correct 1752 ms 295368 KB Output is correct
3 Correct 1412 ms 260132 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1845 ms 253512 KB Output is correct
2 Correct 3550 ms 598664 KB Output is correct
3 Correct 1868 ms 256152 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1859 ms 258104 KB Output is correct
2 Correct 4399 ms 711128 KB Output is correct
3 Correct 2028 ms 313492 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 339 ms 238520 KB Output is correct
2 Correct 3836 ms 597936 KB Output is correct
3 Correct 1536 ms 262368 KB Output is correct