結果
問題 | No.1917 LCMST |
ユーザー | inksamurai |
提出日時 | 2022-04-30 21:15:18 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
MLE
|
実行時間 | - |
コード長 | 1,806 bytes |
コンパイル時間 | 2,398 ms |
コンパイル使用メモリ | 213,384 KB |
実行使用メモリ | 814,508 KB |
最終ジャッジ日時 | 2023-09-12 13:04:54 |
合計ジャッジ時間 | 67,550 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 6 ms
5,668 KB |
testcase_01 | AC | 6 ms
5,672 KB |
testcase_02 | AC | 6 ms
5,748 KB |
testcase_03 | AC | 8 ms
5,840 KB |
testcase_04 | AC | 8 ms
5,940 KB |
testcase_05 | AC | 9 ms
6,064 KB |
testcase_06 | AC | 8 ms
6,060 KB |
testcase_07 | AC | 8 ms
6,120 KB |
testcase_08 | AC | 6 ms
5,712 KB |
testcase_09 | AC | 1,722 ms
279,648 KB |
testcase_10 | AC | 1,777 ms
279,528 KB |
testcase_11 | AC | 1,775 ms
279,764 KB |
testcase_12 | AC | 1,678 ms
279,636 KB |
testcase_13 | AC | 1,706 ms
279,000 KB |
testcase_14 | AC | 1,713 ms
279,872 KB |
testcase_15 | AC | 1,676 ms
277,684 KB |
testcase_16 | AC | 1,716 ms
279,688 KB |
testcase_17 | AC | 1,743 ms
279,160 KB |
testcase_18 | AC | 1,703 ms
280,500 KB |
testcase_19 | AC | 1,311 ms
279,168 KB |
testcase_20 | AC | 1,264 ms
277,584 KB |
testcase_21 | AC | 1,332 ms
278,628 KB |
testcase_22 | AC | 1,218 ms
277,404 KB |
testcase_23 | AC | 1,247 ms
277,324 KB |
testcase_24 | AC | 1,295 ms
277,756 KB |
testcase_25 | AC | 1,240 ms
277,764 KB |
testcase_26 | AC | 1,241 ms
278,856 KB |
testcase_27 | AC | 1,354 ms
279,228 KB |
testcase_28 | AC | 1,319 ms
280,020 KB |
testcase_29 | AC | 1,910 ms
279,564 KB |
testcase_30 | AC | 1,869 ms
280,472 KB |
testcase_31 | AC | 1,874 ms
280,736 KB |
testcase_32 | AC | 1,891 ms
280,996 KB |
testcase_33 | AC | 1,850 ms
280,208 KB |
testcase_34 | AC | 1,714 ms
276,792 KB |
testcase_35 | AC | 590 ms
84,264 KB |
testcase_36 | AC | 2,012 ms
275,648 KB |
testcase_37 | AC | 1,904 ms
280,620 KB |
testcase_38 | AC | 1,913 ms
280,308 KB |
testcase_39 | AC | 1,851 ms
280,332 KB |
testcase_40 | AC | 1,913 ms
280,700 KB |
testcase_41 | AC | 1,833 ms
280,036 KB |
testcase_42 | AC | 1,845 ms
280,192 KB |
testcase_43 | MLE | - |
testcase_44 | MLE | - |
ソースコード
#include <bits/stdc++.h> using namespace std; #define rep(i,n) for(int i=0;i<n;i++) #define rng(i,x,n) for(int i=x;i<n;i++) #define per(i,n) for(int i=n-1;i>=0;i--) #define fi first #define se second #define pb push_back #define sz(a) (int)a.size() #define vec(...) vector<__VA_ARGS__> #define _3k5NXAD ios::sync_with_stdio(0),cin.tie(0) typedef long long ll; using pii=pair<int,int>; using vi=vector<int>; void print(){cout<<'\n';} template<class h,class...t> void print(const h&v,const t&...u){cout<<v<<' ',print(u...);} // e struct dsu{ int n,cmps; vector<int> par,siz; dsu(int m){init(m);} void init(int m){ n=m; cmps=m; par.resize(n,0); siz.resize(n,0); for(int i=0;i<n;i++){ par[i]=i; siz[i]=1; } } void merge(int v,int u){ v=parent(v),u=parent(u); if(v==u)return; if(siz[v]<siz[u])swap(v,u); cmps-=1; siz[v]+=siz[u]; par[u]=v; } int parent(int v){ return par[v]==v?v:parent(par[v]); } bool same(int v, int u){ return parent(v)==parent(u); } int size(int v=-1){ return (v==-1?cmps:siz[parent(v)]); } }; const int nax=100001; vi rbts[nax]; signed main(){ _3k5NXAD; int n; cin>>n; vi a(n); rep(i,n){ cin>>a[i]; } rep(i,n){ rbts[a[i]].pb(i); } using tup=tuple<ll,int,int>; vec(tup) edges; rng(i,1,nax){ int rt=-1,irt=-1; for(int j=i;j<nax;j+=i){ if(sz(rbts[j])){ rt=j; irt=rbts[j][0]; break; } } if(rt==-1) continue; for(int j=rt+i;j<nax;j+=i){ for(auto &u:rbts[j]){ // print(irt,rt,i,j,u); edges.pb({(1ll*rt*j)/i,u,irt}); } } if(rt!=-1){ for(auto &u:rbts[rt]){ edges.pb({(1ll*rt*rt)/i,u,irt}); } } } sort(edges.begin(),edges.end()); dsu uf(n); ll ans=0; for(auto &[cosu,u,v]:edges){ if(uf.same(u,v)) continue; ans+=cosu; uf.merge(u,v); } print(ans); // return 0; }