結果
問題 | No.2428 Returning Shuffle |
ユーザー |
![]() |
提出日時 | 2023-08-19 10:48:22 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 880 ms / 2,000 ms |
コード長 | 829 bytes |
コンパイル時間 | 164 ms |
コンパイル使用メモリ | 81,960 KB |
実行使用メモリ | 246,804 KB |
最終ジャッジ日時 | 2024-11-29 02:33:53 |
合計ジャッジ時間 | 7,149 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 |
ソースコード
MOD = 998244353from math import lcmdef root(x):if P[x] < 0: return xP[x] = root(P[x]) # 経路圧縮return P[x]def unite(x, y):x = root(x)y = root(y)if x == y: returnif x > y: x, y = y, xP[x] += P[y]P[y] = xdef same(x, y):return root(x) == root(y)def size(x):x = root(x)return -P[x]N, M = map(int, input().split())P = [-1] * NP1 = list(range(N))for _ in range(M):t, *S = map(int, input().split())s0 = P1[S[0] - 1]n = len(S)for i in reversed(range(n)):if i == 0:P1[S[(i + 1) % t] - 1] = s0continueP1[S[(i + 1) % t] - 1] = P1[S[i] - 1]for i, p in enumerate(P1):unite(i, p)tmp = 1for i in range(N):if i == root(i):s = size(i)tmp = lcm(tmp,s)print(tmp % MOD)