oj.uz

Submission #1053795

# Submission time Handle Problem Language Result Execution time Memory
1053795 2024-08-11T17:39:54 Z Tam_theguide Sirni (COCI17_sirni) C++17
84 / 140
 406 ms 786436 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());

    if (p[0] == 1) return cout << 0, 0;
    
    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 - 1; 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]);
    }

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

    Init_Dsu();

    long long 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 7 ms 39772 KB Output is correct
2 Correct 92 ms 89784 KB Output is correct
3 Correct 7 ms 40024 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Runtime error 314 ms 786432 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 39768 KB Output is correct
2 Correct 6 ms 39772 KB Output is correct
3 Correct 7 ms 40028 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 32840 KB Output is correct
2 Correct 162 ms 57668 KB Output is correct
3 Correct 87 ms 58436 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 11004 KB Output is correct
2 Correct 117 ms 57412 KB Output is correct
3 Correct 52 ms 30780 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 57788 KB Output is correct
2 Correct 223 ms 107832 KB Output is correct
3 Correct 88 ms 32840 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 9808 KB Output is correct
2 Correct 276 ms 107376 KB Output is correct
3 Correct 79 ms 34120 KB Output is correct

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 66108 KB Output is correct
2 Runtime error 401 ms 786436 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 66376 KB Output is correct
2 Runtime error 371 ms 786432 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 43276 KB Output is correct
2 Runtime error 406 ms 786432 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -