結果

問題 No.2756 GCD Teleporter
ユーザー novaandcabralnovaandcabral
提出日時 2024-06-11 17:06:31
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 2,480 bytes
コンパイル時間 2,170 ms
コンパイル使用メモリ 187,836 KB
実行使用メモリ 8,320 KB
最終ジャッジ日時 2024-06-11 17:06:39
合計ジャッジ時間 8,067 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 AC 4 ms
5,376 KB
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 AC 29 ms
5,376 KB
testcase_13 AC 140 ms
8,192 KB
testcase_14 AC 126 ms
7,936 KB
testcase_15 AC 30 ms
5,376 KB
testcase_16 AC 72 ms
6,656 KB
testcase_17 AC 88 ms
6,912 KB
testcase_18 AC 29 ms
5,376 KB
testcase_19 AC 139 ms
8,320 KB
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 AC 63 ms
5,888 KB
testcase_29 AC 94 ms
6,528 KB
testcase_30 AC 120 ms
7,296 KB
testcase_31 AC 52 ms
5,632 KB
testcase_32 AC 86 ms
7,168 KB
testcase_33 AC 35 ms
5,376 KB
testcase_34 AC 16 ms
5,376 KB
testcase_35 AC 98 ms
7,040 KB
testcase_36 AC 90 ms
7,040 KB
testcase_37 AC 3 ms
5,376 KB
testcase_38 AC 146 ms
7,296 KB
testcase_39 AC 184 ms
7,168 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'int main()':
main.cpp:96:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
   96 |         for (auto [k, v] : F.get(a)) {
      |                   ^
main.cpp:105:14: warning: overflow in conversion from 'long long int' to 'int' changes value from '9223372036854775807' to '-1' [-Woverflow]
  105 |     int mi = LLONG_MAX;
      |              ^~~~~~~~~
main.cpp:107:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
  107 |         for (auto [k, v] : F.get(A[i])) {
      |                   ^

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

class Factorization {
public:
    vector<int> L;

    Factorization(int N) {
        L.resize(N + 1);
        for (int i = 0; i <= N; ++i) {
            L[i] = i;
        }
        for (int i = 2; i <= N; ++i) {
            if (i != L[i]) continue;
            for (int j = 2 * i; j <= N; j += i) {
                L[j] = i;
            }
        }
    }

    vector<pair<int, int>> get(int n) {
        vector<pair<int, int>> D;
        if (n <= 1) return D;
        while (n != 1) {
            int cnt = 0;
            int now = L[n];
            while (n % now == 0) {
                cnt++;
                n /= now;
            }
            D.push_back({now, cnt});
        }
        return D;
    }
};

class UnionFind {
public:
    vector<int> par, rank, size;

    UnionFind(int n) {
        par.resize(n);
        rank.resize(n, 0);
        size.resize(n, 1);
        for (int i = 0; i < n; ++i) {
            par[i] = i;
        }
    }

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

    void union_sets(int x, int y) {
        x = find(x);
        y = find(y);
        if (x != y) {
            if (rank[x] < rank[y]) {
                swap(x, y);
            }
            if (rank[x] == rank[y]) {
                rank[x]++;
            }
            par[y] = x;
            size[x] += size[y];
        }
    }

    bool is_same(int x, int y) {
        return find(x) == find(y);
    }

    int get_size(int x) {
        return size[find(x)];
    }
};

int main() {
    int N;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }

    const int M = 2 * 100000 + 5;
    Factorization F(M);
    int now = N;

    unordered_map<int, int> D;
    for (int a : A) {
        for (auto [k, v] : F.get(a)) {
            if (D.find(k) == D.end()) {
                D[k] = now;
                now++;
            }
        }
    }

    UnionFind U(now);
    int mi = LLONG_MAX;
    for (int i = 0; i < N; ++i) {
        for (auto [k, v] : F.get(A[i])) {
            mi = min(mi, k);
            U.union_sets(i, D[k]);
        }
    }

    set<int> S;
    for (int i = 0; i < N; ++i) {
        S.insert(U.find(i));
    }

    if (mi == 2) {
        cout << (S.size() - 1) * 2 << endl;
    } else {
        cout << min(2 * S.size(), mi * (S.size() - 1)) << endl;
    }

    return 0;
}
0