結果
| 問題 | No.1365 [Cherry 1st Tune] Whose Fault? |
| ユーザー |
👑  Kazun
|
| 提出日時 | 2020-12-23 02:05:13 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 6,851 bytes |
| コンパイル時間 | 305 ms |
| コンパイル使用メモリ | 82,432 KB |
| 実行使用メモリ | 67,072 KB |
| 最終ジャッジ日時 | 2024-06-09 06:41:23 |
| 合計ジャッジ時間 | 4,217 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| 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].discard(B)
self.adjacent_in [B].discard(P)
#(Y,not G) → (X,F)を除く
self.adjacent_out[Q].discard(A)
self.adjacent_in [A].discard(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=[]
for _ in range(M):
C=tuple(map(int,input().split()))
E.append(C)
K=[["*","*"]]
T=Two_SAT(N+1)
THREE=[]
for i in range(1,N+1):
t,*L=input()[:-1].split()
t=int(t)
L=list(L)
if t==1:
L.append(-1)
T.add_clause(i,0,i,0)
elif t==2:
pass
else:
THREE.append(i)
K.append(L)
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=[x for x in K[a] if x in 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[0]
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:
if K[a][0]==K[b][0]:
T.add_clause(a,0,b,1)
T.add_clause(a,1,b,0)
else:
T.add_clause(a,0,b,0)
T.add_clause(a,1,b,1)
Index={THREE[i]:i for i in range(len(THREE))}
THREE_COLOR=[K[v] for v in THREE]
for U in product(*THREE_COLOR):
Flag=True
#タイプ2をチェック
for a,b,c in Cond[2]:
alpha=Index[a]
beta =Index[b]
if c==0:
if U[alpha]==U[beta]:
Flag=False
break
else:
if U[alpha]!=U[beta]:
Flag=False
break
if not Flag:
continue
#タイプ1を追加
A=[]
for a,b,c in Cond[1]:
if a not in THREE:
a,b=b,a
if c==0:
for s in [0,1]:
if U[Index[a]]==K[b][s]:
if not T.clause_exist(b,1-s,b,1-s):
A.append((b,1-s,c))
else:
for s in [0,1]:
if U[Index[a]]!=K[b][s]:
if not T.clause_exist(b,1-s,b,1-s):
A.append((b,1-s,c))
for b,u,c in A:
T.add_clause(b,u,b,u)
X=T.Is_Satisfy(1)
if X:
C=[0]*(N+1)
for i in range(1,N+1):
if i in THREE:
C[i]=U[Index[i]]
else:
C[i]=K[i][X[i]]
print("Possible")
for i in range(1,N+1):
print(C[i])
exit(0)
for b,u,c in A:
T.remove_clause(b,u,b,u)
print("Fault")