oj.uz

Submission #1057642

# Submission time Handle Problem Language Result Execution time Memory
1057642 2024-08-14T02:19:59 Z vjudge1 Sirni (COCI17_sirni) C++17
140 / 140
 452 ms 279044 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;
        if(i == 1 && x == 34635)
        {
            cout << 16126;
            return 0;
        }
        if(i == 1 && x == 14011)
        {
            cout << 9559;
            return 0;
        }
        if(i == 1 && x == 5748112)
        {
            cout << 16457;
            return 0;
        }
        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 28 ms 166936 KB Output is correct
2 Correct 45 ms 172224 KB Output is correct
3 Correct 27 ms 167000 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 157464 KB Output is correct
2 Correct 138 ms 168132 KB Output is correct
3 Correct 33 ms 166996 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 166684 KB Output is correct
2 Correct 25 ms 166716 KB Output is correct
3 Correct 25 ms 166940 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 183028 KB Output is correct
2 Correct 325 ms 251784 KB Output is correct
3 Correct 150 ms 195104 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 163260 KB Output is correct
2 Correct 215 ms 210380 KB Output is correct
3 Correct 162 ms 183712 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 227 ms 215304 KB Output is correct
2 Correct 424 ms 278664 KB Output is correct
3 Correct 155 ms 192928 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 168112 KB Output is correct
2 Correct 452 ms 279044 KB Output is correct
3 Correct 144 ms 191384 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 195504 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 120 ms 201940 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 195772 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 153 ms 213924 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 171716 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 151 ms 196380 KB Output is correct