結果
問題 | No.2756 GCD Teleporter |
ユーザー | GOTKAKO |
提出日時 | 2024-05-10 22:37:41 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 133 ms / 2,000 ms |
コード長 | 2,467 bytes |
コンパイル時間 | 2,999 ms |
コンパイル使用メモリ | 229,452 KB |
実行使用メモリ | 27,264 KB |
最終ジャッジ日時 | 2024-05-10 22:37:50 |
合計ジャッジ時間 | 7,546 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 57 ms
21,500 KB |
testcase_01 | AC | 54 ms
21,556 KB |
testcase_02 | AC | 58 ms
21,548 KB |
testcase_03 | AC | 56 ms
21,592 KB |
testcase_04 | AC | 57 ms
21,848 KB |
testcase_05 | AC | 75 ms
22,872 KB |
testcase_06 | AC | 111 ms
24,916 KB |
testcase_07 | AC | 105 ms
24,216 KB |
testcase_08 | AC | 98 ms
24,048 KB |
testcase_09 | AC | 88 ms
23,724 KB |
testcase_10 | AC | 116 ms
24,656 KB |
testcase_11 | AC | 109 ms
25,328 KB |
testcase_12 | AC | 70 ms
22,368 KB |
testcase_13 | AC | 119 ms
25,668 KB |
testcase_14 | AC | 121 ms
25,172 KB |
testcase_15 | AC | 75 ms
22,412 KB |
testcase_16 | AC | 116 ms
23,688 KB |
testcase_17 | AC | 100 ms
23,940 KB |
testcase_18 | AC | 73 ms
22,356 KB |
testcase_19 | AC | 133 ms
25,552 KB |
testcase_20 | AC | 102 ms
24,640 KB |
testcase_21 | AC | 80 ms
22,980 KB |
testcase_22 | AC | 99 ms
24,948 KB |
testcase_23 | AC | 62 ms
21,912 KB |
testcase_24 | AC | 92 ms
24,088 KB |
testcase_25 | AC | 92 ms
24,308 KB |
testcase_26 | AC | 99 ms
24,500 KB |
testcase_27 | AC | 99 ms
24,848 KB |
testcase_28 | AC | 84 ms
23,468 KB |
testcase_29 | AC | 98 ms
24,336 KB |
testcase_30 | AC | 112 ms
25,220 KB |
testcase_31 | AC | 80 ms
23,116 KB |
testcase_32 | AC | 86 ms
24,264 KB |
testcase_33 | AC | 91 ms
22,672 KB |
testcase_34 | AC | 64 ms
22,000 KB |
testcase_35 | AC | 94 ms
24,452 KB |
testcase_36 | AC | 87 ms
24,444 KB |
testcase_37 | AC | 62 ms
21,536 KB |
testcase_38 | AC | 91 ms
24,940 KB |
testcase_39 | AC | 95 ms
27,264 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; class UnionFind{ public: vector<int> par,siz; vector<bool> have2,have3; void make(int N){ par.resize(N,-1); siz.resize(N,1); have2.resize(N); have3.resize(N); } int root(int x){ if(par.at(x) == -1) return x; else return par.at(x) = root(par.at(x)); } void unite(int u, int v){ u = root(u),v = root(v); if(u == v) return; if(siz.at(u) < siz.at(v)) swap(u,v); par.at(v) = u; siz.at(u) += siz.at(v); have2.at(u) = (have2.at(u)||have2.at(v)); have3.at(u) = (have3.at(u)||have3.at(v)); } bool issame(int u, int v){ if(root(u) == root(v)) return true; else return false; } }; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int Need = 200000; vector<vector<pair<int,int>>> Pf(Need+1); vector<bool> prime(Need+1,true); prime.at(0) = false; prime.at(1) = false; for(int i=2; i<=Need; i++){ if(!prime.at(i)) continue; Pf.at(i) = {{i,1}}; for(int k=i+i; k<=Need; k+=i){ prime.at(k) = false; int f = 0,k2 = k; while(k2%i == 0) f++,k2 /= i; Pf.at(k).push_back({i,f}); } } int N; cin >> N; UnionFind Z; Z.make(N); vector<vector<int>> fac(Need); for(int i=0; i<N; i++){ int a; cin >> a; for(auto[p,e] : Pf.at(a)) fac.at(p).push_back(i); if(a%2 == 0) Z.have2.at(i) = true; if(a%3 == 0) Z.have3.at(i) = true; } int group = N; for(int i=0; i<Need; i++){ int siz=fac.at(i).size(); for(int k=0; k<siz-1; k++){ int pos1 = fac.at(i).at(k),pos2 = fac.at(i).at(k+1); if(Z.issame(pos1,pos2)) continue; group--; Z.unite(pos1,pos2); } } int answer = 0; set<int> leader; for(int i=0; i<N; i++) leader.insert(Z.root(i)); if(group == 2){ bool two = false,three = false; for(auto pos : leader){ if(Z.have2.at(pos)) two = true; if(Z.have3.at(pos)) three = true; } if(two) answer = 2; else if(three) answer = 3; else answer = 4; } else if(group >= 3){ bool two = false; for(auto pos : leader) if(Z.have2.at(pos)) two = true; answer = 2*group; if(two) answer -= 2; } cout << answer << endl; }