oj.uz

Submission #1114513

# Submission time Handle Problem Language Result Execution time Memory
1114513 2024-11-19T06:49:47 Z 0x34c Sirni (COCI17_sirni) C++17
140 / 140
 2584 ms 479780 KB 
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define endl '\n'

using namespace std;

const int MAX_P = 1e7 + 1;

int cnt[MAX_P], nxt[MAX_P];

struct edge
{
    int a, b, w;
};

class DSU
{
private:
    vector<int> rank, par;

public:
    int comps;
    DSU(int n)
    {
        comps = n;
        rank.resize(n, 0);
        par.resize(n, 0);
        iota(par.begin(), par.end(), 0);
    }

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

    bool uni(int a, int b)
    {
        a = find(a);
        b = find(b);
        if (a == b)
            return false;
        if (rank[b] > rank[a])
            swap(a, b);
        par[b] = a;
        if (rank[a] == rank[b])
            rank[a]++;
        --comps;
        return true;
    }
};

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

    int N;
    cin >> N;

    vector<int> arr(N);
    for (int i = 0; i < N; i++)
        cin >> arr[i];

    sort(arr.begin(), arr.end());
    arr.erase(unique(arr.begin(), arr.end()), arr.end());
    N = arr.size();

    map<int, int> conv;
    for (int i = 0; i < N; i++)
    {
        conv[arr[i]] = i;
        cnt[arr[i]]++;
    }

    int j = 0;
    for (int i = 0; i < N; i++)
    {
        while (j < arr[i])
        {
            nxt[j] = arr[i];
            j++;
        }
    }

    while (j < MAX_P)
    {
        nxt[j] = -1;
        j++;
    }

    vector<edge> edges;
    for (int i = 1; i < MAX_P; i++)
    {
        if (!cnt[i])
            continue;
        for (int k = i; k < MAX_P; k += i)
        {
            if (cnt[k] > 0 && i != k)
            {
                edges.push_back({i, k, 0});
                continue;
            }
            if (nxt[k] == -1)
                break;
            if (k <= nxt[k] && nxt[k] < k + i)
                edges.push_back({i, nxt[k], nxt[k] % k});
        }
    }

    sort(edges.begin(), edges.end(), [&](edge &a, edge &b)
         { return a.w < b.w; });

    DSU dsu(N);
    ll res = 0;
    for (edge &e : edges)
    {
        if (dsu.uni(conv[e.a], conv[e.b]))
            res += e.w;
        if (dsu.comps == 1)
            break;
    }

    cout << res << endl;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 78672 KB Output is correct
2 Correct 48 ms 82380 KB Output is correct
3 Correct 17 ms 78928 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 41984 KB Output is correct
2 Correct 198 ms 79456 KB Output is correct
3 Correct 21 ms 78928 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 78832 KB Output is correct
2 Correct 16 ms 70480 KB Output is correct
3 Correct 20 ms 78672 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 256 ms 62912 KB Output is correct
2 Correct 570 ms 99556 KB Output is correct
3 Correct 175 ms 74440 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 48068 KB Output is correct
2 Correct 162 ms 95924 KB Output is correct
3 Correct 286 ms 60096 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 487 ms 99760 KB Output is correct
2 Correct 493 ms 148888 KB Output is correct
3 Correct 188 ms 75184 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 50624 KB Output is correct
2 Correct 442 ms 148136 KB Output is correct
3 Correct 150 ms 74680 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 319 ms 110532 KB Output is correct
2 Correct 1748 ms 479780 KB Output is correct
3 Correct 357 ms 110476 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 110516 KB Output is correct
2 Correct 2584 ms 479108 KB Output is correct
3 Correct 208 ms 110256 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 83400 KB Output is correct
2 Correct 2529 ms 478596 KB Output is correct
3 Correct 172 ms 74932 KB Output is correct