結果
問題 | No.1917 LCMST |
ユーザー |
👑 ![]() |
提出日時 | 2022-04-29 22:42:48 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 292 ms / 4,000 ms |
コード長 | 1,413 bytes |
コンパイル時間 | 1,126 ms |
コンパイル使用メモリ | 111,748 KB |
最終ジャッジ日時 | 2025-01-28 23:29:27 |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 42 |
ソースコード
#include <iostream>#include <vector>#include <algorithm>#include <map>#include <cmath>#include <atcoder/modint>#include <atcoder/dsu>using namespace std;using i32 = int;using u32 = unsigned int;using i64 = long long;using u64 = unsigned long long;#define rep(i,n) for(int i=0; i<(int)(n); i++)using m32 = atcoder::static_modint<1000000007>;const int Z = 100000;int main(){int N; cin >> N;vector<int> A(Z+1);u64 ans = 0;rep(i,N){int a; cin >> a;if(A[a]) ans += a;A[a] = 1;}atcoder::dsu dsu(Z+1);vector<pair<int, int>> V(Z+1, make_pair(Z+1, -1));for(int z=Z; z>=1; z--) for(int p=z; p<=Z; p+=z) if(A[p]) V[z] = min(V[z], make_pair(p / z, p));for(int z=Z; z>=1; z--) for(int p=z; p<=Z; p+=z) if(A[p]) V[p] = min(V[p], V[z]);vector<pair<i64, pair<int, int>>> edges;for(int z=Z; z>=1; z--) for(int p=z; p<=Z; p+=z) if(A[p]) if(V[z].first != Z+1){edges.push_back(make_pair((i64)V[z].first * p, make_pair(V[z].second, p)));}sort(edges.begin(), edges.end());for(auto [d,e] : edges){if(dsu.same(e.first, e.second)) continue;dsu.merge(e.first, e.second);ans += d;}cout << ans << '\n';return 0;}struct ios_do_not_sync{ios_do_not_sync(){std::ios::sync_with_stdio(false);std::cin.tie(nullptr);}} ios_do_not_sync_instance;