結果
問題 | No.1917 LCMST |
ユーザー | inksamurai |
提出日時 | 2022-04-30 21:09:50 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
MLE
|
実行時間 | - |
コード長 | 1,843 bytes |
コンパイル時間 | 3,781 ms |
コンパイル使用メモリ | 215,960 KB |
実行使用メモリ | 814,328 KB |
最終ジャッジ日時 | 2023-09-12 13:01:33 |
合計ジャッジ時間 | 85,584 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 6 ms
5,388 KB |
testcase_01 | AC | 6 ms
5,420 KB |
testcase_02 | AC | 6 ms
5,420 KB |
testcase_03 | AC | 8 ms
5,972 KB |
testcase_04 | AC | 9 ms
6,024 KB |
testcase_05 | AC | 8 ms
5,968 KB |
testcase_06 | AC | 9 ms
6,064 KB |
testcase_07 | AC | 8 ms
6,044 KB |
testcase_08 | AC | 6 ms
5,348 KB |
testcase_09 | AC | 2,598 ms
420,388 KB |
testcase_10 | AC | 2,376 ms
420,408 KB |
testcase_11 | AC | 2,282 ms
420,508 KB |
testcase_12 | AC | 2,193 ms
420,084 KB |
testcase_13 | AC | 2,207 ms
420,268 KB |
testcase_14 | AC | 2,256 ms
420,104 KB |
testcase_15 | AC | 2,122 ms
418,196 KB |
testcase_16 | AC | 2,231 ms
419,676 KB |
testcase_17 | AC | 2,276 ms
420,068 KB |
testcase_18 | AC | 2,229 ms
420,608 KB |
testcase_19 | AC | 1,831 ms
419,068 KB |
testcase_20 | AC | 1,740 ms
418,304 KB |
testcase_21 | AC | 1,906 ms
418,388 KB |
testcase_22 | AC | 1,726 ms
418,120 KB |
testcase_23 | AC | 1,752 ms
417,836 KB |
testcase_24 | AC | 1,774 ms
418,440 KB |
testcase_25 | AC | 1,721 ms
418,588 KB |
testcase_26 | AC | 1,741 ms
420,528 KB |
testcase_27 | AC | 1,849 ms
420,912 KB |
testcase_28 | AC | 1,822 ms
420,148 KB |
testcase_29 | AC | 2,439 ms
420,392 KB |
testcase_30 | AC | 2,413 ms
420,400 KB |
testcase_31 | AC | 2,422 ms
420,280 KB |
testcase_32 | AC | 2,457 ms
420,536 KB |
testcase_33 | AC | 2,410 ms
420,320 KB |
testcase_34 | AC | 2,244 ms
420,628 KB |
testcase_35 | AC | 768 ms
130,572 KB |
testcase_36 | AC | 2,614 ms
420,656 KB |
testcase_37 | AC | 2,422 ms
420,564 KB |
testcase_38 | AC | 2,454 ms
420,420 KB |
testcase_39 | AC | 2,351 ms
420,488 KB |
testcase_40 | AC | 2,422 ms
420,232 KB |
testcase_41 | AC | 2,384 ms
420,476 KB |
testcase_42 | AC | 2,378 ms
420,588 KB |
testcase_43 | MLE | - |
testcase_44 | MLE | - |
ソースコード
#include <bits/stdc++.h> #define int ll 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)]); } }; signed main(){ _3k5NXAD; int n; cin>>n; vi a(n); rep(i,n){ cin>>a[i]; } const int nax=100001; vec(vi) rbts(nax); rep(i,n){ rbts[a[i]].pb(i); } using tup=tuple<int,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({(rt*j)/i,u,irt}); } } if(rt!=-1){ for(auto &u:rbts[rt]){ edges.pb({(rt*rt)/i,u,irt}); } } } sort(edges.begin(),edges.end()); dsu uf(n); int ans=0; for(auto &[cosu,u,v]:edges){ if(uf.same(u,v)) continue; // print(u,v,cosu); ans+=cosu; uf.merge(u,v); } print(ans); // return 0; }