結果
| 問題 | No.2293 無向辺 2-SAT |
| ユーザー |
 t98slider
|
| 提出日時 | 2023-05-09 02:20:01 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 1,154 bytes |
| コンパイル時間 | 400 ms |
| コンパイル使用メモリ | 87,192 KB |
| 実行使用メモリ | 270,572 KB |
| 最終ジャッジ日時 | 2023-08-16 23:43:17 |
| 合計ジャッジ時間 | 16,406 ms |
|
ジャッジサーバーID （参考情報） |
judge14 / judge13 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 79 ms
75,652 KB |
| testcase_01 | AC | 114 ms
101,168 KB |
| testcase_02 | AC | 77 ms
71,392 KB |
| testcase_03 | AC | 620 ms
120,184 KB |
| testcase_04 | TLE | - |
| testcase_05 | AC | 2,335 ms
270,200 KB |
| testcase_06 | TLE | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
| testcase_36 | -- | - |
| testcase_37 | -- | - |
| testcase_38 | -- | - |
| testcase_39 | -- | - |
| testcase_40 | -- | - |
| testcase_41 | -- | - |
| testcase_42 | -- | - |
| testcase_43 | -- | - |
| testcase_44 | -- | - |
| testcase_45 | -- | - |
| testcase_46 | -- | - |
| testcase_47 | -- | - |
| testcase_48 | -- | - |
| testcase_49 | -- | - |
| testcase_50 | -- | - |
| testcase_51 | -- | - |
| testcase_52 | -- | - |
| testcase_53 | -- | - |
| testcase_54 | -- | - |
| testcase_55 | -- | - |
ソースコード
from sys import stdin
I = stdin.readline
J, R = int, range
X = I().split()
N, Q, P, p, w = J(X[0]), J(X[1]), 998244353, [], []
pow2 = [0] * (N + 1)
pow2[0] = 1
for i in range(N):
pow2[i + 1] = pow2[i] + pow2[i]
pow2[i + 1] %= 998244353
def r(i):
m = p[i]
while i != m:
p[i] = i = p[m]
m = p[i]
return i
n = 0
def g(i, j):
global n
i, j = r(i), r(j)
if i != j:
if w[i] == w[j] : w[j] += 1
if w[i] < w[j] : p[i] = j
else: p[j] = i
n -= 1
U, V, W, T, L, f = [0] * N, [0] * N, [0] * N, [(0,)] * Q, 0, pow(2, N, P)
while Q:
for l in R(L): V[W[l]] = 0
M, L, s = 0, 0, 1
while Q:
Q, X = Q - 1, I().split()
t = J(X[0])
if t == 3:
T[M], M = ((t,)), M + 1
break
else:
u, v = J(X[1]) - 1, J(X[2]) - 1
if V[u] == 0: U[u], V[u], W[L], L = L, 1, u, L+1
if V[v] == 0: U[v], V[v], W[L], L = L, 1, v, L+1
T[M], M = ((t,u,v)), M + 1
n = N * 2
p = [i for i in R(n)]
w = [0] * n
for l in T[:M]:
if l[0] == 3: print(f)
else:
if s:
u, v = U[l[1]], U[l[2]]
t = u + L
if l[0] == 1: g(u,v), g(t,v+L)
else: g(t, v), g(u, v + L)
if p[r(u)] == p[r(t)] : s=0
print(pow2[n // 2] if s else 0)