Submission #1114513

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114513		0x34c	Sirni (COCI17_sirni)	C++17	140 / 140	2584 ms	479780 KiB

sirni

#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 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 14 / 14
• Subtask 8: 14 / 14
• Subtask 9: 14 / 14
• Subtask 10: 14 / 14