結果

問題 No.1917 LCMST
ユーザー Koi
提出日時 2025-07-16 00:14:34
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 746 ms / 4,000 ms
コード長 1,762 bytes
コンパイル時間 3,935 ms
コンパイル使用メモリ 307,528 KB
実行使用メモリ 88,208 KB
最終ジャッジ日時 2025-07-16 00:15:05
合計ジャッジ時間 29,072 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 42
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
#include<atcoder/dsu>
using namespace atcoder;
const int M = 100000;

int main(){
  // cerr << "HI\n";
  vector<vector<int>> L(M + 1);
  for(int i = 1; i < M + 1; i++){
    int x = i;
    while(x <= M){
      L[x].push_back(i);
      x += i;
    }
  }
  // cerr << "HI\n";


  int N;
  cin >> N;
  vector<long long> A(N);
  for(int i = 0; i < N; i++){
    cin >> A[i];
  }
  long long ans = 0;
  unordered_set<long long> S;
  for(int i = 0; i < N; i++){
    if(S.count(A[i]) == 1){
      ans += A[i];
    }else{
      S.insert(A[i]);
    }
  }
  A.clear();
  for(long long x: S){
    A.push_back(x);
  }
  N = (int)A.size();
  vector<vector<pair<long long, int>>> D(M + 1);
  vector<tuple<long long, int, int>> Es;
  for(int i = 0; i < N; i++){
    for(int p:L[A[i]]){
      // cerr << i << "\n";
      D[p].push_back({A[i], i});
    }
  }
  for(int i = 1; i < M + 1; i++){
    vector<pair<long long, int>> &L = D[i]; 
    if(L.size() > 1){
      long long best = 1000000;
      int best_ind = -1;
      for(int j = 0; j < L.size(); j++){
        if(best > L[j].first){
          best = L[j].first;
          best_ind = j;
        }
      }
      for(int j = 0; j < L.size(); j++){
        if(j != best_ind){

          long long cost = L[best_ind].first * L[j].first / i;
          //cerr << L[best_ind].second << " " << L[j].second << " " << cost << "\n";
          Es.push_back({cost, L[best_ind].second, L[j].second});
        }
      }
    }
  }

  sort(Es.begin(), Es.end());
  dsu d(N);
  for(auto cost_i_j : Es){
    long long cost = get<0>(cost_i_j);
    int i = get<1>(cost_i_j);
    int j = get<2>(cost_i_j);
    if(!d.same(i, j)){
      d.merge(i, j);
      ans += cost;
    }
  }
  cout << ans << "\n";
}
0