結果
| 問題 |
No.1365 [Cherry 1st Tune] Whose Fault?
|
| コンテスト | |
| ユーザー |
👑  Kazun
|
| 提出日時 | 2020-12-25 17:52:39 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 7,901 bytes |
| コンパイル時間 | 586 ms |
| コンパイル使用メモリ | 81,920 KB |
| 実行使用メモリ | 66,816 KB |
| 最終ジャッジ日時 | 2024-12-29 09:18:54 |
| 合計ジャッジ時間 | 6,187 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | RE * 46 |
ソースコード
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=[["*","*"]]
G=Two_SAT(N+1)
T=[0]*(N+1)
Many=[]
for i in range(1,N+1):
T[i],*L=input()[:-1].split()
T[i]=int(T[i])
L=tuple(L)
if T[i]==1:
L+=(-1,)
G.add_clause(i,0,i,0)
elif T[i]==2:
pass
else:
Many.append(i)
if T[i]==3 or T[i]==5:
L+=(-1,)
K.append(L)
Lazy=[]
for a,b,c in E:
if a in Many or b in Many:
Lazy.append((a,b,c))
else:
if c==0:
for s in [0,1]:
for t in [0,1]:
if K[a][s]==K[b][t]:
G.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:
#矛盾
G.add_clause(0,0,0,0)
G.add_clause(0,1,0,1)
elif len(H)==1:
h=H[0]
s=K[a].index(h)
t=K[b].index(h)
G.add_clause(a,s,a,s)
G.add_clause(b,t,b,t)
else:
if K[a][0]==K[b][0]:
G.add_clause(a,0,b,1)
G.add_clause(a,1,b,0)
else:
G.add_clause(a,0,b,0)
G.add_clause(a,1,b,1)
Index={v:i for i,v in enumerate(Many)}
Many_COLOR=[[(K[j][2*p],K[j][2*p+1]) for p in range(len(K[j])//2)] for j in Many]
for U in product(*Many_COLOR):
Flag=True
for i in range(len(Many)):
K[Many[i]]=U[i]
A=[]
for v in Many:
if K[v][1]==-1 and not G.clause_exist(v,0,v,0):
A.append((v,0,v,0))
G.add_clause(v,0,v,0)
for a,b,c in Lazy:
if a not in Many:
a,b=b,a
if c==0:
for s in [0,1]:
for t in [0,1]:
if K[a][s]==K[b][t] and not G.clause_exist(a,1-s,b,1-t):
A.append((a,1-s,b,1-t))
G.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:
#矛盾
if not G.clause_exist(0,0,0,0):
A.append((0,0,0,0))
G.add_clause(0,0,0,0)
if not G.clause_exist(0,1,0,1):
A.append((0,1,0,1))
G.add_clause(0,1,0,1)
elif len(H)==1:
h=H[0]
s=K[a].index(h)
t=K[b].index(h)
if not G.clause_exist(a,s,a,s):
A.append(a,s,a,s)
G.add_clause(a,s,a,s)
if not G.clause_exist(b,t,b,t):
A.append(b,t,b,t)
G.add_clause(b,t,b,t)
else:
if K[a][0]==K[b][0]:
if not G.add_clause(a,0,b,1):
A.append(a,0,b,1)
G.add_clause(a,0,b,1)
if not G.add_clause(a,1,b,1):
A.append(a,1,b,0)
G.add_clause(a,1,b,0)
else:
if not G.clause_exist(a,0,b,0):
A.append(a,0,b,0)
G.add_clause(a,0,b,0)
if not G.clause_exist(a,1,b,1):
A.append(a,1,b,1)
G.add_clause(a,1,b,1)
X=G.Is_Satisfy(1)
if X!=None:
S=""
for i in range(1,N+1):
S+=K[i][X[i]]
print(S)
exit(0)
for B in A:
G.remove_clause(*B)
print("Fault")