結果
| 問題 | No.3827 MST on LCM Graph |
| コンテスト | |
| ユーザー |
|
| 提出日時 | 2026-11-15 16:49:58 |
| 言語 | C++23 (gcc 15.3.0 + boost 1.92.0 + ACL) |
| 結果 |
TLE
不安定
|
| 実行時間 | - |
| コード長 | 1,807 bytes |
| 記録 | |
| コンパイル時間 | 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 |
ソースコード
#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;
}