結果
問題 | No.274 The Wall |
ユーザー | recuraki |
提出日時 | 2020-02-04 12:53:19 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 399 ms / 2,000 ms |
コード長 | 4,449 bytes |
コンパイル時間 | 581 ms |
コンパイル使用メモリ | 86,980 KB |
実行使用メモリ | 87,440 KB |
最終ジャッジ日時 | 2023-09-04 02:47:43 |
合計ジャッジ時間 | 7,478 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 147 ms
78,592 KB |
testcase_01 | AC | 146 ms
78,656 KB |
testcase_02 | AC | 152 ms
78,596 KB |
testcase_03 | AC | 177 ms
83,268 KB |
testcase_04 | AC | 146 ms
78,408 KB |
testcase_05 | AC | 144 ms
78,768 KB |
testcase_06 | AC | 148 ms
78,252 KB |
testcase_07 | AC | 147 ms
78,600 KB |
testcase_08 | AC | 146 ms
78,476 KB |
testcase_09 | AC | 145 ms
78,660 KB |
testcase_10 | AC | 145 ms
78,248 KB |
testcase_11 | AC | 177 ms
81,372 KB |
testcase_12 | AC | 220 ms
82,232 KB |
testcase_13 | AC | 189 ms
79,732 KB |
testcase_14 | AC | 264 ms
85,500 KB |
testcase_15 | AC | 327 ms
86,768 KB |
testcase_16 | AC | 174 ms
81,316 KB |
testcase_17 | AC | 173 ms
81,520 KB |
testcase_18 | AC | 175 ms
81,408 KB |
testcase_19 | AC | 371 ms
85,844 KB |
testcase_20 | AC | 387 ms
86,136 KB |
testcase_21 | AC | 385 ms
86,740 KB |
testcase_22 | AC | 399 ms
87,440 KB |
testcase_23 | AC | 389 ms
86,512 KB |
testcase_24 | AC | 393 ms
87,144 KB |
testcase_25 | AC | 391 ms
87,024 KB |
ソースコード
import sys sys.setrecursionlimit(200000) from collections import deque # a-zに正方向と逆辺を張る def addEdge(g, a, z): g[0][a].append(z) g[1][z].append(a) g[0][z].append(a) g[1][a].append(z) # グラフの初期化 def initGraph(g, edgenum): g.append([]) # [0] 正方向のグラフ g.append([]) # [1] 逆方向のグラフ for _ in range(edgenum): g[0].append(deque(list())) for _ in range(edgenum): g[1].append(deque(list())) def dfs(g, v, visited, vs): # 正方向のDFS visited[v] = True for i in range(len(g[0][v])): if visited[g[0][v][i]] is False: dfs(g, g[0][v][i], visited, vs) vs.append(v) def rdfs(g, v, visited, cmp, k): # 逆方向のDFS # kがcall元に指定される連結成分の通し番号 visited[v] = True cmp[v] = k # 指定したノードの逆辺をたどる for i in range(len(g[1][v])): # print("go? {0}".format(g[1][v][i])) # 逆辺の先がrDFSで到達できないときのみ if visited[g[1][v][i]] is False: # print("yes") rdfs(g, g[1][v][i], visited, cmp, k) def scc(g, cmp): vs = [] # 帰りがけのリスト visited = [False] * len(g[0]) cmp.extend([None] * len(g[0])) for i in range(len(g[0])): if visited[i] is False: dfs(g, i, visited, vs) visited = [False] * len(g[1]) k = 0 # pprint(vs) for i in range(len(vs) - 1, -1, -1): # print("vited: i={0} vs[i] = {1}".format(i, vs[i])) # print(visited) if visited[vs[i]] is False: # print("rdfs [{0}]".format(i)) rdfs(g, vs[i], visited, cmp, k) k += 1 # pprint(vs) return k n, m = map(int, input().split()) dat = [] for _ in range(n): a,b = map(int, input().split()) dat.append((a,b)) f = True vCount = n * 2 # 各xとnot x分で2倍 # 0-n-1が各要素のx, n - n*2-1がnot x の 領域 g = [] # グラフ。[0] = 正方向のグラフ。 [1] = 逆方向のグラフ cmp = [] from pprint import pprint initGraph(g, edgenum=vCount) def isSafe(a, b, c, d): a,b,c,d = min(a,b), max(a,b), min(c,d), max(c,d) #print("{0} {1} {2} {3}".format(a,b,c,d)) if a < c and b < c: #print("T") return True if a > d and b > d: #print("T2") return True #print("{0} {1} {2} {3}".format(a,b,c,d)) #print("F") return False for i in range(n): if f is False: break # あくまで縦のほかとの一致なので for j in range(i+1, n): if isSafe(dat[i][0], dat[i][1], dat[j][0], dat[j][1]) is False: # もし、そのままで通らない場合、 if isSafe((m-1) - dat[i][0], (m-1) - dat[i][1], dat[j][0], dat[j][1]): # 自分を反転して通るのであれば not x → y, あるいはx → not yなのだから addEdge(g, n + i, j) addEdge(g, i, n + j) else: # 何をしても通らないので通らないダミーパスを作る f = False break else: # そのままで通る場合で if isSafe((m-1) - dat[i][0], (m-1) - dat[i][1], dat[j][0], dat[j][1]) is False: # 反転させてしまうと通らないのであれば、 x → y あるいは not x → not yなのだから addEdge(g, i, j) addEdge(g, n + i, n + j) else: pass # 回転させても通るならなにをしても通るので制約は要らない """ if isSafe(dat[i][0], dat[i][1], dat[pi][0], dat[pi][1]) is False: addEdge(g, n + i, n + pi) if isSafe(m - dat[i][0], m - dat[i][1], dat[pi][0], dat[pi][1]) is False: addEdge(g, i, n + pi) if isSafe(dat[i][0], dat[i][1], m - dat[pi][0], m - dat[pi][1]) is False: addEdge(g, n + i, pi) if isSafe(m - dat[i][0], m - dat[i][1], m - dat[pi][0], m - dat[pi][1]) is False: addEdge(g, i, pi) """ if f is False: print("NO") else: k = scc(g, cmp) #pprint(g) f = True for i in range(n): if cmp[i] == cmp[n+i]: #print("hit{0} {1}, by {2} {3}".format(cmp[i], cmp[n+i], i, n+i)) f = False break #print(cmp) print("YES" if f else "NO")