oj.uz

Submission #1109879

# Submission time Handle Problem Language Result Execution time Memory
1109879 2024-11-08T01:59:26 Z juliany2 Sirni (COCI17_sirni) C++17
140 / 140
 1099 ms 581460 KB 
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) (x).begin(), (x).end()

struct DSU {
    vector<int> e;

    DSU(int sz) { e = vector<int> (sz + 1, -1); }

    int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }

    bool unite(int u, int v) {
        u = get(u), v = get(v);
        if (u == v) return false;
        if (e[v] < e[u]) swap(u, v);
        e[u] += e[v], e[v] = u;
        return true;
    }
};

const int M = 1e7 + 7;
int n;
int nxt[M];
vector<array<int, 2>> e[M];

int main() {
    cin.tie(0)->sync_with_stdio(false);

    memset(nxt, -1, sizeof(nxt));

    cin >> n;

    vector<int> a(n);
    for (int &i : a)
        cin >> i;

    sort(all(a));
    a.erase(unique(all(a)), a.end());

    n = a.size();
    for (int i = 0; i < n; i++) {
        nxt[a[i]] = i;
    }

    for (int i = M - 2; i >= 0; i--) {
        if (nxt[i] == -1)
            nxt[i] = nxt[i + 1];
    }

    for (int i = 0; i < n; i++) {
        vector<int> l;

        if (~nxt[a[i] + 1])
            l.push_back(nxt[a[i] + 1]);

        for (int j = a[i] * 2; j < M; j += a[i]) {
            if (nxt[j] == -1)
                break;
            l.push_back(nxt[j]);
        }

        l.erase(unique(all(l)), l.end());

        for (int j : l) {
            e[a[j] % a[i]].push_back({i, j});
        }
    }

    DSU dsu(n);

    ll ans = 0;
    for (int i = 0; i < M; i++) {
        for (auto &[u, v] : e[i]) {
            if (dsu.unite(u, v)) {
                ans += i;
            }
        }

        if (-dsu.e[dsu.get(1)] == n)
            break;
    }

    cout << ans << '\n';

    return 0;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 274504 KB Output is correct
2 Correct 77 ms 276776 KB Output is correct
3 Correct 52 ms 274504 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 274424 KB Output is correct
2 Correct 351 ms 309384 KB Output is correct
3 Correct 50 ms 274772 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 274504 KB Output is correct
2 Correct 48 ms 274336 KB Output is correct
3 Correct 52 ms 274624 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 285436 KB Output is correct
2 Correct 150 ms 319676 KB Output is correct
3 Correct 101 ms 290376 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 275984 KB Output is correct
2 Correct 120 ms 297032 KB Output is correct
3 Correct 100 ms 286436 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 301164 KB Output is correct
2 Correct 179 ms 337136 KB Output is correct
3 Correct 101 ms 288964 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 278088 KB Output is correct
2 Correct 192 ms 325192 KB Output is correct
3 Correct 95 ms 288700 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 287144 KB Output is correct
2 Correct 751 ms 494856 KB Output is correct
3 Correct 119 ms 290264 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 287448 KB Output is correct
2 Correct 1099 ms 581460 KB Output is correct
3 Correct 155 ms 310452 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 276672 KB Output is correct
2 Correct 1014 ms 570684 KB Output is correct
3 Correct 102 ms 289980 KB Output is correct