結果

問題 No.3827 MST on LCM Graph
コンテスト
ユーザー 259-Momone
提出日時 2026-11-15 20:56:47
言語 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,348 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,693 ms
コンパイル使用メモリ 212,360 KB
実行使用メモリ 161,920 KB
最終ジャッジ日時 2026-11-22 12:43:31
合計ジャッジ時間 24,017 ms
ジャッジサーバーID
(参考情報)
judge1_0 / judge5_0
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 25 TLE * 3
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code

#include <iostream>
#include <vector>
#include <algorithm>
#include <ranges>
#include <set>
#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<optional<unsigned>> values(M + 1);
    unsigned long ans{};
    for (const auto &[i, a] : A | views::enumerate) if (!values[a])
        values[a] = i;
    else
        ans += a;


    set<tuple<unsigned long, unsigned, unsigned>> edges;
    for (unsigned i{1}; i <= M; ++i)
        for (unsigned j{i}, mn{N}, mx{}; j <= M; j += i)
            if (values[j]) {
                mn = min(mn, *values[j]);
                mx = max(mx, *values[j]);
                edges.emplace(lcm(A[mn] + 0ul, A[mx]), mn, mx);
            }

    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