oj.uz

Submission #1092869

# Submission time Handle Problem Language Result Execution time Memory
1092869 2024-09-25T09:23:09 Z vjudge1 Sirni (COCI17_sirni) C++14
140 / 140
 2653 ms 435116 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 21 ms 39504 KB Output is correct
2 Correct 40 ms 42612 KB Output is correct
3 Correct 18 ms 39708 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 856 KB Output is correct
2 Correct 21 ms 40404 KB Output is correct
3 Correct 17 ms 39772 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 39512 KB Output is correct
2 Correct 16 ms 39504 KB Output is correct
3 Correct 18 ms 39556 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 17484 KB Output is correct
2 Correct 261 ms 54976 KB Output is correct
3 Correct 100 ms 30264 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 7604 KB Output is correct
2 Correct 176 ms 54896 KB Output is correct
3 Correct 75 ms 16176 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 54228 KB Output is correct
2 Correct 348 ms 104160 KB Output is correct
3 Correct 97 ms 30268 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 7504 KB Output is correct
2 Correct 331 ms 104152 KB Output is correct
3 Correct 90 ms 30272 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 64804 KB Output is correct
2 Correct 1690 ms 435116 KB Output is correct
3 Correct 151 ms 65596 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 65316 KB Output is correct
2 Correct 2561 ms 435072 KB Output is correct
3 Correct 185 ms 65596 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 43012 KB Output is correct
2 Correct 2653 ms 434868 KB Output is correct
3 Correct 101 ms 30524 KB Output is correct