結果
問題 | No.2293 無向辺 2-SAT |
ユーザー |
👑 ![]() |
提出日時 | 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 |
ソースコード
class RollBack_Union_Find():__slots__=["n", "parents", "__history", "__snap_time", "__group_count"]def __init__(self, N):""" 0,1,...,N-1 を要素として初期化する.N: 要素数"""self.n=Nself.parents=[-1]*Nself.__history=[]self.__snap_time=[]self.__group_count=[]def find(self, x):""" 要素 x の属している族を調べる.x: 要素"""while self.parents[x]>=0:x=self.parents[x]return xdef union(self, x, y):""" 要素 x,y を同一視する.[input]x,y: 要素[output]元々が非連結 → True元々が連結 → False"""x=self.find(x); y=self.find(y)par=self.parentsself.__history.append((x, par[x]))self.__history.append((y, par[y]))if self.__group_count:count=self.__group_count[-1]else:count=self.nif x==y:self.__group_count.append(count)return Falseif par[x]>par[y]:x,y=y,xpar[x]+=par[y]par[y]=xself.__group_count.append(count-1)return Truedef 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.ndef get_time(self):return len(self.__history)>>1def undo(self):""" 1 回分の union を戻る."""if self.__history:y,b=self.__history.pop()self.parents[y]=bx,a=self.__history.pop()self.parents[x]=aself.__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:returnif time>self.get_time():returnT=time<<1while 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 Xdef 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 defaultdictN,Q=map(int,input().split())U=RollBack_Union_Find(N)ans=[0]*Qvalid=TrueT=defaultdict(lambda :defaultdict(int))for q in range(Q):mode,*value=map(int,input().split())if mode==1 or mode==2:u,v=valueu-=1; v-=1up=U.find(u); vp=U.find(v)mode-=1if up==vp:if T[up][u]!=T[vp][v]^mode:valid=Falseelse:if (up not in T) or (u not in T[up]):T[up][u]=0if (vp not in T) or (v not in T[vp]):T[vp][v]=0if len(T[up])>len(T[vp]):u,v=v,uup,vp=vp,updiff=T[up][up]^T[vp][vp]for v in T[vp]:T[up][v]=T[vp][v]^diff^modeT[vp].clear()U.union(u,v)else:U.rollback(0)T=defaultdict(lambda :defaultdict(int))valid=Trueans[q]=pow(2,U.group_count(),998244353) if valid else 0return ans#==================================================import sysinput=sys.stdin.readlinewrite=sys.stdout.writewrite("\n".join(map(str,solve())))