結果
問題 | No.100 直列あみだくじ |
ユーザー |
![]() |
提出日時 | 2020-05-14 11:32:16 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 5,000 ms |
コード長 | 1,175 bytes |
コンパイル時間 | 1,761 ms |
コンパイル使用メモリ | 178,972 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-15 02:01:34 |
合計ジャッジ時間 | 2,976 ms |
ジャッジサーバーID (参考情報) |
judge6 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 45 |
ソースコード
#include <bits/stdc++.h> using namespace std; struct UnionFind { vector<int> data; UnionFind(int n) { data.assign(n, -1); } bool unite(int x, int y) { x = root(x), y = root(y); if (x == y) return (false); if (data[x] > data[y]) swap(x, y); data[x] += data[y]; data[y] = x; return (true); } int root(int k) { if (data[k] < 0) return (k); return (data[k] = root(data[k])); } bool same(int x, int y) { return root(x) == root(y); } int size(int k) { return (-data[root(k)]); } }; int main() { int N, a[60] = {}; cin >> N; for (int i = 0; i < N; i++) { cin >> a[i]; a[i]--; } UnionFind uf(N); for (int i = 0; i < N; i++) { uf.unite(i, a[i]); } map<int, int> M; for (int i = 0; i < N; i++) { if (uf.root(i) == i && uf.size(i) % 2 == 0) { M[uf.size(i)] += 1; } } for (auto p : M) { if (p.second % 2) { cout << "No" << endl; return 0; } } cout << "Yes" << endl; }