結果
問題 | No.1779 Magical Swap |
ユーザー |
|
提出日時 | 2021-12-08 18:30:53 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 196 ms / 2,000 ms |
コード長 | 1,250 bytes |
コンパイル時間 | 991 ms |
コンパイル使用メモリ | 81,336 KB |
実行使用メモリ | 10,612 KB |
最終ジャッジ日時 | 2024-07-16 08:07:52 |
合計ジャッジ時間 | 2,686 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 18 |
ソースコード
#include <iostream> #include <vector> #include <algorithm> using namespace std; class UnionFind { public: explicit UnionFind(int N) : root(N, -1), size(N, 1) {} int getRoot(int u){ return root[u] == -1 ? u : root[u] = getRoot(root[u]); } int getSize(int u){ return size[getRoot(u)]; } bool same(int a, int b){ return getRoot(a) == getRoot(b); } bool merge(int a, int b){ int u = getRoot(a); int v = getRoot(b); if(u == v) return false; root[u] = v; size[v] += size[u]; return true; } private: vector<int> root; vector<int> size; }; void solve(){ int N; cin >> N; UnionFind uf(N+1); for(int i=2;2*i<=N;i++){ for(int j=2;j*i<=N;j++){ uf.merge(i, j*i); } } vector<vector<int>> ca(N), cb(N); for(int j=1;j<=N;j++){ int t; cin >> t; ca[uf.getRoot(j)-1].push_back(t); } for(int j=1;j<=N;j++){ int t; cin >> t; cb[uf.getRoot(j)-1].push_back(t); } for(auto& s : ca) sort(s.begin(), s.end()); for(auto& s : cb) sort(s.begin(), s.end()); cout << (ca == cb ? "Yes" : "No") << endl; } int main(){ int T; cin >> T; while(T--){ solve(); } }