oj.uz

Submission #1106946

# Submission time Handle Problem Language Result Execution time Memory
1106946 2024-10-31T09:38:25 Z vjudge1 Sirni (COCI17_sirni) C++17
98 / 140
 583 ms 786432 KB 
#include <bits/stdc++.h>
#define int long long
#define ll long long

using namespace std;

const int N = 1e7 + 5;
const int mx = 1e7;

struct Edge {
    int u, v;
    ll c;
    Edge(int _u, int _v, int _c): u(_u), v(_v), c(_c) {};
};

struct Dsu {
    vector<int> par;

    void init(int n) {
        par.resize(n + 5, 0);
        for (int i = 1; i <= n; i++) par[i] = i;
    }

    int find(int u) {
        if (par[u] == u) return u;
        return par[u] = find(par[u]);
    }

    bool join(int u, int v) {
        u = find(u); v = find(v);
        if (u == v) return false;
        par[v] = u;
        return true;
    }
} dsu;

int n, m;
ll totalWeight = 0;
vector < Edge > edges;
int near[N];
bool check[N];

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> n;

    for (int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        check[x] = 1;
    }

    int cur = -1;
    for(int i = mx; i >= 1; i--)
    {
        if(check[i])
            cur = i;
        near[i] = cur;
        if(!check[i])
            continue;
        if(near[i + 1] != -1 && near[i + 1] <= i + i)
        edges.push_back({i, near[i + 1], near[i + 1] % i});
        for(int j = i * 2; j <= mx; j += i)
            if(near[j] != -1 && near[j] <= j + i)
                edges.push_back({i, near[j], near[j] % i});

    }
    dsu.init(mx);

    sort(edges.begin(), edges.end(), [](Edge & x, Edge & y) {
        return x.c < y.c;
    });

    for (auto e : edges)
    {
        if (!dsu.join(e.u, e.v)) continue;
        totalWeight += e.c;
    }

    cout << totalWeight;
    return 0;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 166928 KB Output is correct
2 Correct 68 ms 172720 KB Output is correct
3 Correct 31 ms 166968 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 157096 KB Output is correct
2 Correct 155 ms 168124 KB Output is correct
3 Correct 33 ms 166980 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 166932 KB Output is correct
2 Correct 32 ms 166480 KB Output is correct
3 Correct 31 ms 167004 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 183768 KB Output is correct
2 Correct 375 ms 251692 KB Output is correct
3 Correct 177 ms 196132 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 163252 KB Output is correct
2 Correct 290 ms 210556 KB Output is correct
3 Correct 173 ms 183964 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 276 ms 214688 KB Output is correct
2 Correct 583 ms 279948 KB Output is correct
3 Correct 179 ms 192164 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 169640 KB Output is correct
2 Correct 497 ms 279944 KB Output is correct
3 Correct 166 ms 192148 KB Output is correct

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 195492 KB Output is correct
2 Runtime error 508 ms 786432 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 134 ms 195500 KB Output is correct
2 Runtime error 547 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 53 ms 172980 KB Output is correct
2 Runtime error 583 ms 786432 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -