結果

問題 No.2293 無向辺 2-SAT
ユーザー 👑 Kazun
提出日時 2023-05-05 22:39:41
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 5,029 bytes
コンパイル時間 313 ms
コンパイル使用メモリ 82,560 KB
実行使用メモリ 230,592 KB
最終ジャッジ日時 2024-11-23 10:01:34
合計ジャッジ時間 64,186 ms
ジャッジサーバーID
(参考情報)
judge1 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 15 WA * 38
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

class RollBack_Union_Find():
__slots__=["n", "parents", "__history", "__snap_time", "__group_count"]
def __init__(self, N):
""" 0,1,...,N-1 .
N:
"""
self.n=N
self.parents=[-1]*N
self.__history=[]
self.__snap_time=[]
self.__group_count=[]
def find(self, x):
""" x 調.
x:
"""
while self.parents[x]>=0:
x=self.parents[x]
return x
def union(self, x, y):
""" x,y .
[input]
x,y:
[output]
→ True
→ False
"""
x=self.find(x); y=self.find(y)
par=self.parents
self.__history.append((x, par[x]))
self.__history.append((y, par[y]))
if self.__group_count:
count=self.__group_count[-1]
else:
count=self.n
if x==y:
self.__group_count.append(count)
return False
if par[x]>par[y]:
x,y=y,x
par[x]+=par[y]
par[y]=x
self.__group_count.append(count-1)
return True
def size(self, x):
""" x .
x:
"""
return -self.parents[self.find(x)]
def same(self, x, y):
""" x,y ?
x,y:
"""
return self.find(x) == self.find(y)
def members(self, x):
""" x .
size 使!!
x:
"""
root = self.find(x)
return [i for i in range(self.n) if self.find(i) == root]
def representative(self):
"""
"""
return [i for i, x in enumerate(self.parents) if x < 0]
def group_count(self):
"""
"""
if self.__group_count:
return self.__group_count[-1]
else:
return self.n
def get_time(self):
return len(self.__history)>>1
def undo(self):
""" 1 union .
"""
if self.__history:
y,b=self.__history.pop()
self.parents[y]=b
x,a=self.__history.pop()
self.parents[x]=a
self.__group_count.pop()
def snapshot(self):
"""
"""
self.__snap_time.append(self.get_time())
def rollback(self, time=-1):
""" time .
"""
if time==-1:
if self.__snap_time:
time=self.__snap_time[-1]
else:
return
if time>self.get_time():
return
T=time<<1
while T<len(self.__history):
self.undo()
def all_group_members(self):
"""
"""
X={r:[] for r in self.representative()}
for k in range(self.n):
X[self.find(k)].append(k)
return X
def group_list(self):
""" .
"""
return [self.find(x) for x in range(self.n)]
def __str__(self):
return str(self.all_group_members().values())[13:-2]
def __repr__(self):
return "RollBack Union Find: "+str(self)
def __getitem__(self,index):
return self.find(index)
def __setitem__(self,x,y):
self.union(x,y)
#==================================================
def solve():
from collections import defaultdict
N,Q=map(int,input().split())
U=RollBack_Union_Find(N)
ans=[0]*Q
valid=True
T=defaultdict(lambda :defaultdict(int))
for q in range(Q):
mode,*value=map(int,input().split())
if mode==1 or mode==2:
u,v=value
u-=1; v-=1
up=U.find(u); vp=U.find(v)
mode-=1
if up==vp:
if T[up][u]!=T[vp][v]^mode:
valid=False
else:
if (up not in T) or (u not in T[up]):
T[up][u]=0
if (vp not in T) or (v not in T[vp]):
T[vp][v]=0
if len(T[up])>len(T[vp]):
u,v=v,u
up,vp=vp,up
diff=T[up][up]^T[vp][vp]
for v in T[vp]:
T[up][v]=T[vp][v]^diff^mode
T[vp].clear()
U.union(u,v)
else:
U.rollback(0)
T=defaultdict(lambda :defaultdict(int))
valid=True
ans[q]=pow(2,U.group_count(),998244353) if valid else 0
return ans
#==================================================
import sys
input=sys.stdin.readline
write=sys.stdout.write
write("\n".join(map(str,solve())))
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0