結果
| 問題 | No.1365 [Cherry 1st Tune] Whose Fault? |
| ユーザー |
👑  Kazun
|
| 提出日時 | 2020-12-22 04:39:57 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 6,671 bytes |
| コンパイル時間 | 235 ms |
| コンパイル使用メモリ | 82,176 KB |
| 実行使用メモリ | 66,688 KB |
| 最終ジャッジ日時 | 2024-06-09 06:39:51 |
| 合計ジャッジ時間 | 5,591 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | RE | - |
| testcase_01 | RE | - |
| testcase_02 | RE | - |
| testcase_03 | RE | - |
| testcase_04 | RE | - |
| testcase_05 | RE | - |
| testcase_06 | RE | - |
| testcase_07 | RE | - |
| testcase_08 | RE | - |
| testcase_09 | RE | - |
| testcase_10 | RE | - |
| testcase_11 | RE | - |
| testcase_12 | RE | - |
| testcase_13 | RE | - |
| testcase_14 | RE | - |
| testcase_15 | RE | - |
| testcase_16 | RE | - |
| testcase_17 | RE | - |
| testcase_18 | RE | - |
| testcase_19 | RE | - |
| testcase_20 | RE | - |
| testcase_21 | RE | - |
| testcase_22 | RE | - |
| testcase_23 | RE | - |
| testcase_24 | RE | - |
| testcase_25 | RE | - |
| testcase_26 | RE | - |
| testcase_27 | RE | - |
| testcase_28 | RE | - |
| testcase_29 | RE | - |
| testcase_30 | RE | - |
| testcase_31 | RE | - |
| testcase_32 | RE | - |
| testcase_33 | RE | - |
| testcase_34 | RE | - |
| testcase_35 | RE | - |
| testcase_36 | RE | - |
| testcase_37 | RE | - |
| testcase_38 | RE | - |
| testcase_39 | RE | - |
| testcase_40 | RE | - |
| testcase_41 | RE | - |
| testcase_42 | RE | - |
| testcase_43 | RE | - |
| testcase_44 | RE | - |
| testcase_45 | RE | - |
ソースコード
class Two_SAT:
"""2-SATを定義する.
"""
#※ i:変数 i が Trueの頂点, i+N:変数 i がFalseの頂点
#入力定義
def __init__(self,N):
"""N変数の2-SATを考える.
"""
self.N=N
self.clause_number=0
self.adjacent_out=[set() for k in range(2*N)] #出近傍(vが始点)
self.adjacent_in=[set() for k in range(2*N)] #入近傍(vが終点)
#節の追加
def add_clause(self,X,F,Y,G):
"""(X=F) or (Y=G) という節を加える.
X,Y:変数の名前
F,G:真偽値(True or False)
"""
assert 0<=X<self.N and 0<=Y<self.N
F=bool(F);G=bool(G)
(A,P)=(X,X+self.N) if F else (X+self.N,X)
(B,Q)=(Y,Y+self.N) if G else (Y+self.N,Y)
if not self.clause_exist(X,F,Y,G):
self.clause_number+=1
#(X,not F)→(Y,G)を追加
self.adjacent_out[P].add(B)
self.adjacent_in [B].add(P)
#(Y,not G) → (X,F)を追加
self.adjacent_out[Q].add(A)
self.adjacent_in [A].add(Q)
#節を除く
def remove_clause(self,X,F,Y,G):
"""(X=F) or (Y=G) という節を除く.
X,Y:変数の名前
F,G:真偽値(True or False)
"""
assert 0<=X<self.N and 0<=Y<self.N
F=bool(F);G=bool(G)
(A,P)=(X,X+self.N) if F else (X+self.N,X)
(B,Q)=(Y,Y+self.N) if G else (Y+self.N,Y)
if not self.clause_exist(X,F,Y,G):
return
self.clause_number-=1
#(X,not F)→(Y,G)を除く
self.adjacent_out[P].remove(B)
self.adjacent_in [B].remove(P)
if X==Y and F==G:
return
#(Y,not G) → (X,F)を除く
self.adjacent_out[Q].remove(A)
self.adjacent_in [A].remove(Q)
#グラフに節が存在するか否か
def clause_exist(self,X,F,Y,G):
"""(X=F) or (Y=G) という節が存在するか?
X,Y:変数の名前
F,G:真偽値(True or False)
"""
assert 0<=X<self.N and 0<=Y<self.N
(A,P)=(X,X+self.N) if F else (X+self.N,X)
(B,Q)=(Y,Y+self.N) if G else (Y+self.N,Y)
return B in self.adjacent_out[P]
#近傍
def neighbohood(self,v):
pass
#出次数
def out_degree(self,v):
pass
#入次数
def in_degree(self,v):
pass
#次数
def degree(self,v):
pass
#変数の数
def variable_count(self):
return self.N
#節の数
def clause_count(self):
return self.clause_number
#充足可能?
def Is_Satisfy(self,Mode=0):
"""充足可能?
Mode:
0(Defalt)---充足可能?
1 ---充足可能ならば,その変数の割当を変える.(不可能なときはNone)
2 ---充足不能の原因である変数を全て挙げる.
"""
from collections import deque
N=self.N
Group=[0]*(2*N)
Order=[]
for s in range(2*N):
if Group[s]:continue
S=deque([s])
Group[s]=-1
while S:
u=S.pop()
for v in self.adjacent_out[u]:
if Group[v]:continue
Group[v]=-1
S.append(u);S.append(v)
break
else:
Order.append(u)
K=0
for s in Order[::-1]:
if Group[s]!=-1:continue
S=deque([s])
Group[s]=K
while S:
u=S.pop()
for v in self.adjacent_in[u]:
if Group[v]!=-1:continue
Group[v]=K
S.append(v)
K+=1
if Mode==0:
for i in range(N):
if Group[i]==Group[i+N]:
return False
return True
elif Mode==1:
T=[0]*N
for i in range(N):
if Group[i]>Group[i+N]:
T[i]=1
elif Group[i]==Group[i+N]:
return None
return T
elif Mode==2:
return [i for i in range(N) if Group[i]==Group[i+N]]
#================================================
import sys
from itertools import product
input=sys.stdin.readline
N,M=map(int,input().split())
E=[map(int,input().split()) for _ in range(M)]
T=Two_SAT(N+1)
K=[["*","*"]]
THREE=set()
for i in range(1,N+1):
t,*L=map(int,input().split())
L.sort()
if t==1:
K.append(L+[-i])
T.add_clause(i,False,i,False)
elif t==2:
K.append(L)
else:
K.append(L)
THREE.add(i)
Cond=[[],[],[]]
for a,b,c in E:
w=(a in THREE)+(b in THREE)
Cond[w].append((a,b,c))
#タイプ0を処理
for a,b,c in Cond[0]:
if c==0:
for s in [0,1]:
for t in [0,1]:
if K[a][s]==K[b][t]:
T.add_clause(a,1-s,b,1-t)
else:
H=set(K[a]) & set(K[b])
if len(H)==0:
#矛盾する論理式
T.add_clause(0,0,0,0)
T.add_clause(0,1,0,1)
elif len(H)==1:
h=H.pop()
s=K[a].index(h)
t=K[b].index(h)
T.add_clause(a,s,a,s)
T.add_clause(b,t,b,t)
else:
#節 x_a←→x_b を加える
T.add_clause(a,1,b,0)
T.add_clause(a,0,b,1)
#THREEの頂点の彩色を全探索
Index={v:i for i,v in enumerate(THREE)}
for G in product([0,1,2],repeat=len(THREE)):
Flag=True
#タイプ2をチェック
for a,b,c in Cond[2]:
alpha=Index[a]
beta =Index[b]
if c==0:
if K[a][G[alpha]]==K[b][G[beta]]:
Flag=False
else:
if K[a][G[alpha]]!=K[b][G[beta]]:
Flag=False
if not Flag:
continue
#タイプ1の条件を追加
Added=[]
for a,b,c in Cond[1]:
if a not in THREE:
a,b=b,a
if c==0:
for d in [0,1]:
if K[a][G[Index[a]]]==K[b][d]:
T.add_clause(b,1-d,b,1-d)
Added.append((b,1-d,b,1-d))
else:
for d in [0,1]:
if K[a][G[Index[a]]]!=K[b][d]:
T.add_clause(b,1-d,b,1-d)
Added.append((b,1-d,b,1-d))
X=T.Is_Satisfy(1)
if X:
print("Possible")
for i in range(1,N+1):
if i in THREE:
print(K[i][G[Index[i]]])
else:
print(K[i][X[i]])
exit(0)
for V in Added:
T.remove_clause(*V)
print("Fault")