結果

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

コンパイルメッセージ
main.cpp:16:3: error: elements of array 'P edge [1066750]' have incomplete type
   16 | P edge[1066750];
      |   ^~~~
main.cpp:16:3: error: storage size of 'edge' isn't known
main.cpp: In lambda function:
main.cpp:40:53: error: no matching function for call to 'get<0>(P&)'
   40 |   sort(edge,edge+edgecnt,[](P& l,P& r){return get<0>(l)<get<0>(r);});
      |                                               ~~~~~~^~~
In file included from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/stl_algobase.h:64,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/string:50,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/locale_classes.h:40,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/ios_base.h:41,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/ios:42,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/ostream:38,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/iostream:39,
                 from main.cpp:4:
/home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/stl_pair.h:855:5: note: candidate: '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
      |     ^~~
/home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/stl_pair.h:855:5: note:   template argument deduction/substitution failed:
main.cpp:40:53: note:   '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);});
      |                                               ~~~~~~^~~
/home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/stl_pair.h:860:5: note: candidate: 'temp

ソースコード

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