結果

問題 No.1917 LCMST
ユーザー kiyoshi0205kiyoshi0205
提出日時 2022-04-30 00:38:14
言語 C++23(draft)
(gcc 12.3.0 + boost 1.83.0)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 920 bytes
コンパイル時間 1,047 ms
コンパイル使用メモリ 99,988 KB
最終ジャッジ日時 2023-09-11 16:27:11
合計ジャッジ時間 4,021 ms
ジャッジサーバーID
(参考情報)
judge12 / judge15
このコードへのチャレンジ(β)
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。(リジャッジ後のコンパイルエラーは公開されます)
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
main.cpp:16:3: エラー: elements of array ‘P edge [1066750]’ have incomplete type
   16 | P edge[1066750];
      |   ^~~~
main.cpp:16:3: エラー: storage size of ‘edge’ isn’t known
main.cpp: ラムダ関数内:
main.cpp:40:53: エラー: ‘get<0>(P&)’ の呼び出しに適合する関数がありません
   40 |   sort(edge,edge+edgecnt,[](P& l,P& r){return get<0>(l)<get<0>(r);});
      |                                               ~~~~~~^~~
次のファイルから読み込み:  /usr/local/gcc7/include/c++/12.2.0/bits/stl_algobase.h:64,
         次から読み込み:  /usr/local/gcc7/include/c++/12.2.0/string:50,
         次から読み込み:  /usr/local/gcc7/include/c++/12.2.0/bits/locale_classes.h:40,
         次から読み込み:  /usr/local/gcc7/include/c++/12.2.0/bits/ios_base.h:41,
         次から読み込み:  /usr/local/gcc7/include/c++/12.2.0/ios:42,
         次から読み込み:  /usr/local/gcc7/include/c++/12.2.0/ostream:38,
         次から読み込み:  /usr/local/gcc7/include/c++/12.2.0/iostream:39,
         次から読み込み:  main.cpp:4:
/usr/local/gcc7/include/c++/12.2.0/bits/stl_pair.h:855:5: 備考: 候補: ‘template<long unsigned int _Int, class _Tp1, class _Tp2> constexpr typename std::tuple_element<_Int, std::pair<_Tp1, _Tp2> >::type& std::get(pair<_Tp1, _Tp2>&)’
  855 |     get(pair<_Tp1, _Tp2>& __in) noexcept
      |     ^~~
/usr/local/gcc7/include/c++/12.2.0/bits/stl_pair.h:855:5: 備考:   template argument deduction/substitution failed:
main.cpp:40:53: 備考:   ‘P’ {aka ‘std::tuple<long long int, int, int>’} is not derived from ‘std::pair<_Tp1, _Tp2>’
   40 |   sort(edge,edge+edgecnt,[](P& l,P& r){return get<0>(l)<get<0>(r);});
      |                                               ~~~~~~^~~
/usr/local/gcc7/include/c++/12.2.0/bits/stl_pair.h:860:5: 備考: 候補: ‘template<long unsigned int _Int, class _Tp1, class _Tp2> constexpr typename std::tuple_element<_Int, std::pair<_Tp1, _Tp2>

ソースコード

diff #

#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include<iostream>
#include<numeric>
using namespace std;
using ll=long long;
using P=tuple<ll,int,int>;
#include<atcoder/dsu>


int N;
ll ans;
bool vis[100001];
int edgecnt;
P edge[1066750];
int main(){
  atcoder::dsu uf(100001);
  cin.tie(0)->sync_with_stdio(0);
  cin>>N;
  while(N--){
    int x;
    cin>>x;
    if(vis[x])ans+=x;
    else vis[x]=true;
  }
  for(int d=1;d<=100000;++d){
    int mi=0;
    for(int k=1;d*k<=100000;++k){
      if(vis[d*k]){
        if(mi){
          auto&[c,u,v]=edge[edgecnt++];
          c=d*lcm<ll>(mi,k);
          u=d*mi;
          v=d*k;
        }else mi=k;
      }
    }
  }
  sort(edge,edge+edgecnt,[](P& l,P& r){return get<0>(l)<get<0>(r);});
  for(int i=0;i<edgecnt;++i){
    auto&[c,u,v]=edge[i];
    if(!uf.same(u,v)){
      uf.merge(u,v);
      ans+=c;
    }
  }
  cout<<ans<<'\n';
}
0