結果
| 問題 | No.3827 MST on LCM Graph |
| コンテスト | |
| ユーザー |
|
| 提出日時 | 2026-11-15 20:43:31 |
| 言語 | C++23 (gcc 15.3.0 + boost 1.92.0 + ACL) |
| 結果 |
AC
不安定
|
| 実行時間 | 288 ms / 2,000 ms |
| + 756µs | |
| コード長 | 1,367 bytes |
| 記録 | |
| コンパイル時間 | 1,547 ms |
| コンパイル使用メモリ | 215,296 KB |
| 実行使用メモリ | 72,864 KB |
| 最終ジャッジ日時 | 2026-11-22 12:43:08 |
| 合計ジャッジ時間 | 6,714 ms |
|
ジャッジサーバーID (参考情報) |
judge2_0 / judge1_0 |
(要ログイン)
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 28 |
ソースコード
#include <iostream>
#include <vector>
#include <algorithm>
#include <ranges>
#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;
vector<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_back(lcm(A[mn] + 0ul, A[mx]), mn, mx);
}
ranges::sort(edges);
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;
}