結果
問題 | No.101 ぐるぐる!あみだくじ! |
ユーザー |
![]() |
提出日時 | 2020-05-14 11:48:19 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3 ms / 5,000 ms |
コード長 | 1,432 bytes |
コンパイル時間 | 1,891 ms |
コンパイル使用メモリ | 176,920 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-15 02:25:05 |
合計ジャッジ時間 | 3,143 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
ソースコード
#include <bits/stdc++.h> using namespace std; long long gcd(long long a, long long b) { while (b) { long long c = b; b = a % b; a = c; } return a; } long long lcm(long long a, long long b) { if (!a || !b) return 0; return a * b / gcd(a, b); } 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, K; cin >> N >> K; int a[110] = {}; for (int i = 0; i < N; i++) { a[i] = i; } while (K--) { int x, y; cin >> x >> y; x--; y--; swap(a[x], a[y]); } UnionFind uf(N); for (int i = 0; i < N; i++) { uf.unite(i, a[i]); } set<long long> S; for (int i = 0; i < N; i++) { S.insert(uf.size(i)); } long long ans = 1; for (auto& x : S) { ans = lcm(ans, x); } cout << ans << endl; }