oj.uz

답안 #1114503

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1114503 2024-11-19T06:39:12 Z 0x34c Sirni (COCI17_sirni) C++17
56 / 140
 2456 ms 479820 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 (nxt[k] == -1)
                break;
            if (cnt[k] > 0 && i != k)
                edges.push_back({i, k, 0});
            else 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
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 78672 KB Output is correct
2 Correct 63 ms 82376 KB Output is correct
3 Correct 21 ms 78928 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 41808 KB Output is correct
2 Correct 203 ms 79492 KB Output is correct
3 Correct 20 ms 78928 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 78672 KB Output is correct
2 Correct 18 ms 70484 KB Output is correct
3 Correct 20 ms 78672 KB Output is correct

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 300 ms 62888 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 48068 KB Output is correct
2 Correct 169 ms 95912 KB Output is correct
3 Incorrect 270 ms 60088 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 550 ms 99760 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 84 ms 50624 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 358 ms 110512 KB Output is correct
2 Correct 1751 ms 479820 KB Output is correct
3 Correct 357 ms 110408 KB Output is correct

Subtask #9
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 203 ms 110508 KB Output is correct
2 Incorrect 2456 ms 476896 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 62 ms 83400 KB Output is correct
2 Incorrect 2434 ms 478568 KB Output isn't correct
3 Halted 0 ms 0 KB -