結果
問題 | No.274 The Wall |
ユーザー | 👑 Kazun |
提出日時 | 2020-11-18 03:55:44 |
言語 | PyPy3 (7.3.15) |
結果 |
MLE
|
実行時間 | - |
コード長 | 3,978 bytes |
コンパイル時間 | 251 ms |
コンパイル使用メモリ | 87,044 KB |
実行使用メモリ | 849,648 KB |
最終ジャッジ日時 | 2023-09-30 14:49:47 |
合計ジャッジ時間 | 7,890 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 72 ms
71,356 KB |
testcase_01 | AC | 71 ms
71,488 KB |
testcase_02 | AC | 72 ms
71,552 KB |
testcase_03 | AC | 1,988 ms
490,492 KB |
testcase_04 | AC | 163 ms
71,348 KB |
testcase_05 | AC | 73 ms
71,436 KB |
testcase_06 | AC | 73 ms
71,468 KB |
testcase_07 | AC | 73 ms
71,296 KB |
testcase_08 | AC | 74 ms
71,468 KB |
testcase_09 | AC | 73 ms
71,404 KB |
testcase_10 | AC | 73 ms
71,408 KB |
testcase_11 | MLE | - |
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 | -- | - |
ソースコード
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_edge(self,X,F,Y,G): pass #グラフに節が存在するか否か 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) """ N=self.N Group=[0]*(2*N) Order=[] for s in range(2*N): if Group[s]:continue S=[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=[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 #================================================ N,M=map(int,input().split()) L =[0]*N;R =[0]*N IL=[0]*N;IR=[0]*N for i in range(N): L[i],R[i]=map(int,input().split()) IL[i],IR[i]=M-1-R[i],M-1-L[i] T=Two_SAT(N) for i in range(N): for j in range(i+1,N): if not(R[i]<L[j] or R[j]<L[i]): T.add_clause(i,1,j,1) if not(IR[i]<L[j] or R[j]<IL[i]): T.add_clause(i,0,j,1) if not(R[i]<IL[j] or IR[j]<L[i]): T.add_clause(i,1,j,0) if not(IR[i]<IL[j] or IR[j]<IL[i]): T.add_clause(i,0,j,0) if T.Is_Satisfy(): print("YES") else: print("NO")