oj.uz

Submission #1053852

# Submission time Handle Problem Language Result Execution time Memory
1053852 2024-08-11T18:39:09 Z Tam_theguide Sirni (COCI17_sirni) C++17
140 / 140
 1870 ms 436100 KB 
#include <bits/stdc++.h>
using namespace std;

struct Edge {
    int u, v, Weight;

    Edge() {}
    Edge(int u, int v, int Weight) :
        u(u), v(v), Weight(Weight) {}
    
    bool operator < (const Edge& other) const {
        return Weight < other.Weight;
    }
};

const int MAXN = 1e5;
const int MAXP = 1e7;

int n, nxt[MAXP + 5], Dsu_pa[MAXN + 5];
vector<int> p;
vector<Edge> Ed;

void Init_Dsu() {
    for (int i = 0; i < n; i++) 
        Dsu_pa[i] = i;
}

int Find_pa(int u) {
    if (u == Dsu_pa[u]) return u;
    return Dsu_pa[u] = Find_pa(Dsu_pa[u]);
}

bool Dsu_Union(int u, int v) {
    u = Find_pa(u);
    v = Find_pa(v);

    if (u == v) return false;

    Dsu_pa[v] = u;
    return true;
}

int main() {
    cin.tie(0) -> ios::sync_with_stdio(0);
    
    cin >> n;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        p.push_back(x);
    }

    sort(p.begin(), p.end());
    p.erase(unique(p.begin(), p.end()), p.end());

    n = p.size();

    for (int i = 0; i < n - 1; i++) {
        nxt[p[i]] = i;
        for (int j = p[i] + 1; j < p[i + 1]; j++)
            nxt[j] = i + 1;
    }

    nxt[p[n - 1]] = n - 1;

    for (int i = 0; i < n; i++) {
        Ed.emplace_back(i, nxt[p[i] + 1], p[nxt[p[i] + 1]] % p[i]);
        for (int mul = 2 * p[i]; mul <= p[n - 1]; mul += p[i]) {
            Ed.emplace_back(i, nxt[mul], p[nxt[mul]] % p[i]);
            mul = p[nxt[mul]] / p[i] * p[i];
        }
    }

    sort(Ed.begin(), Ed.end());

    Init_Dsu();

    int Ans = 0;
    for (auto& c: Ed) 
        if (Dsu_Union(c.u, c.v)) 
            Ans += c.Weight;
    
    cout << Ans;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 39768 KB Output is correct
2 Correct 21 ms 42704 KB Output is correct
3 Correct 10 ms 39964 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 9 ms 40660 KB Output is correct
3 Correct 7 ms 39944 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 39768 KB Output is correct
2 Correct 6 ms 39756 KB Output is correct
3 Correct 8 ms 39956 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 21324 KB Output is correct
2 Correct 186 ms 58164 KB Output is correct
3 Correct 74 ms 32580 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 11008 KB Output is correct
2 Correct 126 ms 58116 KB Output is correct
3 Correct 57 ms 18252 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 58296 KB Output is correct
2 Correct 228 ms 107296 KB Output is correct
3 Correct 72 ms 33496 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 10576 KB Output is correct
2 Correct 239 ms 106280 KB Output is correct
3 Correct 68 ms 33432 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 65816 KB Output is correct
2 Correct 1294 ms 435476 KB Output is correct
3 Correct 111 ms 66052 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 66464 KB Output is correct
2 Correct 1828 ms 435260 KB Output is correct
3 Correct 149 ms 66364 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 44304 KB Output is correct
2 Correct 1870 ms 436100 KB Output is correct
3 Correct 75 ms 33004 KB Output is correct