結果
| 問題 | No.2293 無向辺 2-SAT |
| ユーザー |
 vwxyz
|
| 提出日時 | 2023-11-30 13:05:08 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 5,225 bytes |
| コンパイル時間 | 826 ms |
| コンパイル使用メモリ | 81,700 KB |
| 実行使用メモリ | 280,732 KB |
| 最終ジャッジ日時 | 2023-11-30 13:05:38 |
| 合計ジャッジ時間 | 28,932 ms |
|
ジャッジサーバーID （参考情報） |
judge15 / judge14 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 141 ms
95,488 KB |
| testcase_01 | AC | 199 ms
159,684 KB |
| testcase_02 | AC | 143 ms
88,684 KB |
| testcase_03 | AC | 2,841 ms
280,732 KB |
| testcase_04 | AC | 1,484 ms
173,520 KB |
| testcase_05 | AC | 1,311 ms
136,148 KB |
| testcase_06 | AC | 2,802 ms
132,544 KB |
| testcase_07 | AC | 338 ms
161,472 KB |
| testcase_08 | TLE | - |
| testcase_09 | TLE | - |
| 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 | -- | - |
ソースコード
import bisect
import copy
import decimal
import fractions
import heapq
import itertools
import math
import random
import sys
import time
from collections import Counter,deque,defaultdict
from functools import lru_cache,reduce
from heapq import heappush,heappop,heapify,heappushpop,_heappop_max,_heapify_max
def _heappush_max(heap,item):
heap.append(item)
heapq._siftdown_max(heap, 0, len(heap)-1)
def _heappushpop_max(heap, item):
if heap and item < heap[0]:
item, heap[0] = heap[0], item
heapq._siftup_max(heap, 0)
return item
from math import gcd as GCD
read=sys.stdin.read
readline=sys.stdin.readline
readlines=sys.stdin.readlines
write=sys.stdout.write
#import pypyjit
#pypyjit.set_param('max_unroll_recursion=-1')
#sys.set_int_max_str_digits(10**9)
class UnionFind:
def __init__(self,N,label=None,f=None,weighted=False,rollback=False):
self.N=N
self.parents=[None]*self.N
self.size=[1]*self.N
self.roots={i for i in range(self.N)}
self.label=label
if self.label!=None:
self.label=[x for x in label]
self.f=f
self.weighted=weighted
if self.weighted:
self.weight=[0]*self.N
self.rollback=rollback
if self.rollback:
self.operate_list=[]
self.operate_set=[]
def Find(self,x):
stack=[]
while self.parents[x]!=None:
stack.append(x)
x=self.parents[x]
if not self.rollback:
if self.weighted:
w=0
for y in stack[::-1]:
self.parents[y]=x
w+=self.weight[y]
self.weight[y]=w
else:
for y in stack[::-1]:
self.parents[y]=x
return x
def Union(self,x,y,w=None):
root_x=self.Find(x)
root_y=self.Find(y)
if self.rollback:
self.operate_list.append([])
self.operate_set.append([])
if root_x==root_y:
if self.weighted:
if self.weight[y]-self.weight[x]==w:
return True
else:
return False
else:
if self.size[root_x]<self.size[root_y]:
x,y=y,x
root_x,root_y=root_y,root_x
if self.weighted:
w=-w
if self.rollback:
self.operate_list[-1].append((self.parents,root_y,self.parents[root_y]))
self.operate_list[-1].append((self.size,root_x,self.size[root_x]))
self.operate_set[-1].append(root_y)
if self.label!=None:
self.operate_list[-1]((self.label,root_x,self.label[root_x]))
if self.weighted:
self.operate_list[-1].append((self.weight,root_y,self.weight[root_y]))
self.parents[root_y]=root_x
self.size[root_x]+=self.size[root_y]
self.roots.remove(root_y)
if self.label!=None:
self.label[root_x]=self.f(self.label[root_x],self.label[root_y])
if self.weighted:
self.weight[root_y]=w+self.weight[x]-self.weight[y]
def Size(self,x):
return self.size[self.Find(x)]
def Same(self,x,y):
return self.Find(x)==self.Find(y)
def Label(self,x):
return self.label[self.Find(x)]
def Weight(self,x,y):
root_x=self.Find(x)
root_y=self.Find(y)
if root_x!=root_y:
return None
return self.weight[y]-self.weight[x]
def Roots(self):
return list(self.roots)
def Linked_Components_Count(self):
return len(self.roots)
def Linked_Components(self):
linked_components=defaultdict(list)
for x in range(self.N):
linked_components[self.Find(x)].append(x)
return linked_components
def Rollback(self):
assert self.rollback
if self.operate_list:
for lst,x,v in self.operate_list.pop():
lst[x]=v
for x in self.operate_set.pop():
self.roots.add(x)
return True
else:
return False
def __str__(self):
linked_components=defaultdict(list)
for x in range(self.N):
linked_components[self.Find(x)].append(x)
return "\n".join(f"{r}: {linked_components[r]}" for r in sorted(list(linked_components.keys())))
N,Q=map(int,readline().split())
mod=998244353
UF=UnionFind(2*N,rollback=True)
cnt=0
exist=True
for q in range(Q):
query=tuple(map(int,readline().split()))
if query[0]==2:
_,u,v=query
u-=1;v-=1
UF.Union(u*2,v*2+1)
UF.Union(v*2,u*2+1)
if UF.Same(u*2,u*2+1):
exist=False
cnt+=2
elif query[0]==1:
_,u,v=query
u-=1;v-=1
UF.Union(u*2,v*2)
UF.Union(v*2+1,u*2+1)
if UF.Same(u*2,u*2+1):
exist=False
cnt+=2
else:
for _ in range(cnt):
UF.Rollback()
exist=True
if exist:
ans=pow(2,UF.Linked_Components_Count()//2,mod)
else:
ans=0
print(ans)