oj.uz

Submission #1114501

# Submission time Handle Problem Language Result Execution time Memory
1114501 2024-11-19T06:28:31 Z 0x34c Sirni (COCI17_sirni) C++17
0 / 140
 839 ms 110504 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 = 2 * i; k < MAX_P; k += i)
        {
            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);
    int 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
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 78672 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 41976 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 78672 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 343 ms 62904 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 48 ms 46024 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 839 ms 99764 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 101 ms 50624 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 479 ms 110500 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 478 ms 110504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 76 ms 83392 KB Output isn't correct
2 Halted 0 ms 0 KB -