結果

問題 No.2756 GCD Teleporter
コンテスト
ユーザー novaandcabral
提出日時 2024-06-11 17:06:31
言語 C++14
(gcc 13.3.0 + boost 1.87.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 WA * 3
other AC * 20 WA * 16
権限があれば一括ダウンロードができます
コンパイルメッセージ
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