oj.uz

Submission #226494

# Submission time Handle Problem Language Result Execution time Memory
226494 2020-04-24T01:09:13 Z quocnguyen1012 Sirni (COCI17_sirni) C++14
140 / 140
 3301 ms 711668 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 156 ms 235432 KB Output is correct
2 Correct 222 ms 264696 KB Output is correct
3 Correct 159 ms 235640 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 235384 KB Output is correct
2 Correct 1286 ms 630488 KB Output is correct
3 Correct 153 ms 236024 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 235464 KB Output is correct
2 Correct 148 ms 235320 KB Output is correct
3 Correct 147 ms 235512 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1418 ms 250000 KB Output is correct
2 Correct 1442 ms 277996 KB Output is correct
3 Correct 1068 ms 259792 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 237816 KB Output is correct
2 Correct 261 ms 258424 KB Output is correct
3 Correct 1038 ms 249320 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1552 ms 262152 KB Output is correct
2 Correct 1555 ms 296432 KB Output is correct
3 Correct 1414 ms 258828 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 337 ms 240476 KB Output is correct
2 Correct 1458 ms 295244 KB Output is correct
3 Correct 1176 ms 259984 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1530 ms 253304 KB Output is correct
2 Correct 2723 ms 599204 KB Output is correct
3 Correct 1646 ms 256932 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1574 ms 258020 KB Output is correct
2 Correct 3301 ms 711668 KB Output is correct
3 Correct 1692 ms 314264 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 226 ms 238456 KB Output is correct
2 Correct 2824 ms 598884 KB Output is correct
3 Correct 1207 ms 263120 KB Output is correct