結果
問題 | No.274 The Wall |
ユーザー | brthyyjp |
提出日時 | 2021-09-26 01:20:44 |
言語 | PyPy3 (7.3.15) |
結果 |
MLE
|
実行時間 | - |
コード長 | 2,117 bytes |
コンパイル時間 | 2,038 ms |
コンパイル使用メモリ | 87,036 KB |
実行使用メモリ | 593,692 KB |
最終ジャッジ日時 | 2023-09-19 02:47:36 |
合計ジャッジ時間 | 10,617 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 79 ms
71,204 KB |
testcase_01 | AC | 80 ms
71,288 KB |
testcase_02 | AC | 79 ms
71,440 KB |
testcase_03 | AC | 895 ms
316,700 KB |
testcase_04 | AC | 78 ms
71,384 KB |
testcase_05 | AC | 78 ms
71,308 KB |
testcase_06 | AC | 78 ms
71,120 KB |
testcase_07 | AC | 78 ms
71,496 KB |
testcase_08 | AC | 79 ms
71,320 KB |
testcase_09 | AC | 79 ms
71,524 KB |
testcase_10 | AC | 76 ms
71,516 KB |
testcase_11 | MLE | - |
testcase_12 | AC | 171 ms
77,200 KB |
testcase_13 | AC | 105 ms
76,060 KB |
testcase_14 | AC | 131 ms
78,052 KB |
testcase_15 | AC | 164 ms
78,324 KB |
testcase_16 | AC | 727 ms
195,296 KB |
testcase_17 | AC | 733 ms
189,024 KB |
testcase_18 | AC | 708 ms
202,376 KB |
testcase_19 | AC | 197 ms
79,256 KB |
testcase_20 | AC | 217 ms
79,800 KB |
testcase_21 | AC | 211 ms
79,816 KB |
testcase_22 | AC | 209 ms
79,260 KB |
testcase_23 | AC | 204 ms
79,188 KB |
testcase_24 | AC | 211 ms
79,064 KB |
testcase_25 | AC | 220 ms
79,752 KB |
ソースコード
import sys import io, os sys.setrecursionlimit(10**9) input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline n, m = map(int, input().split()) LR0 = [] LR1 = [] for i in range(n): l, r = map(int, input().split()) LR0.append((l, r)) LR1.append((m-1-r, m-1-l)) g = [[] for i in range(2*n)] rg = [[] for i in range(2*n)] for i in range(n-1): for j in range(i+1, n): li0, ri0 = LR0[i] li1, ri1 = LR1[i] lj0, rj0 = LR0[j] lj1, rj1 = LR1[j] # 区間がかぶる場合を考える cnt = 0 if min(ri0, rj0) >= max(li0, lj0): # ¬xi ∨ ¬xj # xi ⇒ ¬xj, xj ⇒ ¬xi g[i].append(n+j) rg[n+j].append(i) g[j].append(n+i) rg[n+i].append(j) cnt += 1 if min(ri0, rj1) >= max(li0, lj1): # ¬xi ∨ xj # xi ⇒ xj, ¬xj ⇒ ¬xi g[i].append(j) rg[j].append(i) g[n+j].append(n+i) rg[n+i].append(n+j) if min(ri1, rj0) >= max(li1, lj0): # xi ∨ ¬xj # ¬xi ⇒ ¬xj, xj ⇒ xi g[n+i].append(n+j) rg[n+j].append(n+i) g[j].append(i) rg[i].append(j) cnt += 1 if min(ri1, rj1) >= max(li1, lj1): # xi ∨ xj # ¬xi ⇒ xj, ¬xj ⇒ xi g[n+i].append(j) rg[j].append(n+i) g[n+j].append(i) rg[i].append(n+j) cnt += 1 if cnt == 4: print('NO') exit() def dfs(v): used[v] = True for u in g[v]: if not used[u]: dfs(u) vs.append(v) def rdfs(v, k): used[v] = True cmp[v] = k for u in rg[v]: if not used[u]: rdfs(u, k) vs = [] cmp = [-1]*(2*n) used = [False]*(2*n) for v in range(2*n): if not used[v]: dfs(v) k = 0 used = [False]*(2*n) for v in reversed(vs): if not used[v]: k += 1 rdfs(v, k) for i in range(n): if cmp[i] == cmp[n+i]: print('NO') exit() print('YES')