結果

問題 No.3827 MST on LCM Graph
コンテスト
ユーザー 259-Momone
提出日時 2026-11-15 16:49:58
言語 C++23
(gcc 15.3.0 + boost 1.92.0 + ACL)
コンパイル:
g++-15 -O2 -fplugin=/usr/lib/yukicoder/noavx512-gcc15.so -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
TLE  
実行時間 -
コード長 1,807 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,922 ms
コンパイル使用メモリ 224,436 KB
実行使用メモリ 250,224 KB
最終ジャッジ日時 2026-11-22 12:42:59
合計ジャッジ時間 25,914 ms
ジャッジサーバーID
(参考情報)
judge1_0 / judge4_0
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 6 TLE * 5 -- * 17
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code

#include <iostream>
#include <vector>
#include <algorithm>
#include <ranges>
#include <set>
#include <array>
#include <numeric>

int main() {
    using namespace std;
    unsigned N;
    cin >> N;
    vector<unsigned> A(N);
    for (auto&& a : A) cin >> a;
    ranges::sort(A);

    const auto M{ranges::max(A)};
    vector<vector<unsigned>> values(M + 1);
    unsigned long ans{};
    for (const auto &[i, a] : A | views::enumerate) if (empty(values[a]))
        values[a].emplace_back(i);
    else
        ans += a;

    {
        vector<unsigned> tmp;
        vector<unsigned> sieve(M + 1, 1);
        for (unsigned p{2}; p <= M; ++p) if (sieve[p]) {
            for (const auto j : views::iota(1) | views::take_while([p, M](const auto j){return j * p <= M;}) | views::reverse) {
                sieve[j * p] = 0;
                tmp.resize(size(values[j * p]) + size(values[j]));
                swap(tmp, values[j]);
                ranges::merge(values[j * p], tmp, begin(values[j]));
            }
        }
    }

    set<tuple<unsigned long, unsigned, unsigned>> edges;
    for (const auto &vs : values) if (!empty(vs))
        for (const auto first{vs[0]}; const auto rest : vs | views::drop(1))
            edges.emplace(make_tuple(lcm(A[first] + 0ul, A[rest]), first, rest));

    vector<unsigned> uf(N), sz(N, 1);
    iota(begin(uf), end(uf), 0u);
    const auto find{[&uf](auto i) { while (i != uf[i]) i = uf[i] = uf[uf[i]]; return i; }};
    const auto unite{[&uf, &sz, &find](auto i, auto j) {
        i = find(i);
        j = find(j);
        if (i == j) return false;
        if (sz[i] < sz[j]) swap(i, j);
        sz[i] += sz[j];
        uf[j] = i;
        return true;
    }};

    for (const auto& [c, i, j] : edges) if (unite(i, j)) ans += c;

    cout << ans << endl;
    return 0;
}
0