結果
問題 | No.2134 $\sigma$-algebra over Finite Set |
ユーザー | 👑 SPD_9X2 |
提出日時 | 2023-05-11 23:11:29 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,169 bytes |
コンパイル時間 | 310 ms |
コンパイル使用メモリ | 87,316 KB |
実行使用メモリ | 86,848 KB |
最終ジャッジ日時 | 2023-08-18 13:33:16 |
合計ジャッジ時間 | 11,311 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 71 ms
71,464 KB |
testcase_01 | AC | 355 ms
86,848 KB |
testcase_02 | AC | 323 ms
86,620 KB |
testcase_03 | AC | 71 ms
71,192 KB |
testcase_04 | AC | 168 ms
85,988 KB |
testcase_05 | AC | 71 ms
71,324 KB |
testcase_06 | AC | 340 ms
85,364 KB |
testcase_07 | AC | 366 ms
85,372 KB |
testcase_08 | AC | 189 ms
85,312 KB |
testcase_09 | AC | 168 ms
83,252 KB |
testcase_10 | AC | 539 ms
85,484 KB |
testcase_11 | AC | 542 ms
85,656 KB |
testcase_12 | AC | 1,686 ms
85,632 KB |
testcase_13 | TLE | - |
testcase_14 | AC | 205 ms
79,864 KB |
testcase_15 | AC | 241 ms
79,236 KB |
testcase_16 | AC | 221 ms
79,440 KB |
testcase_17 | AC | 72 ms
71,564 KB |
testcase_18 | AC | 72 ms
71,492 KB |
ソースコード
""" https://yukicoder.me/problems/no/2134 """ import sys from sys import stdin def uf_find(n,p): ufl = [] while p[n] != n: ufl.append(n) n = p[n] for i in ufl: p[i] = n return n def uf_union(a,b,p,rank): ap = uf_find(a,p) bp = uf_find(b,p) if ap == bp: return True else: if rank[ap] > rank[bp]: p[bp] = ap elif rank[ap] < rank[bp]: p[ap] = bp else: p[bp] = ap rank[ap] += 1 return False N,M = map(int,stdin.readline().split()) lis = [ [0] * N for i in range(N) ] for loop in range(M): a = list(map(int,stdin.readline().split()))[1:] for i in range(len(a)): a[i] -= 1 a = set(a) b = [] for i in range(N): if i not in a: b.append(i) for i in a: for j in b: lis[i][j] = lis[j][i] = 1 p = [i for i in range(N)] rank = [0] * N for i in range(N): for j in range(i): if lis[i][j] == 0: uf_union(i,j,p,rank) part = 0 for i in range(N): if uf_find(i,p) == i: part += 1 print (pow(2,part,998244353))