結果

問題 No.274 The Wall
ユーザー recurakirecuraki
提出日時 2020-02-04 00:03:39
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,316 bytes
コンパイル時間 227 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 89,216 KB
最終ジャッジ日時 2024-09-19 11:59:52
合計ジャッジ時間 4,509 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 AC 74 ms
75,648 KB
testcase_02 AC 71 ms
75,648 KB
testcase_03 AC 170 ms
85,632 KB
testcase_04 AC 71 ms
75,648 KB
testcase_05 AC 72 ms
75,520 KB
testcase_06 AC 75 ms
75,520 KB
testcase_07 AC 72 ms
75,672 KB
testcase_08 AC 71 ms
75,392 KB
testcase_09 AC 73 ms
75,520 KB
testcase_10 AC 73 ms
75,776 KB
testcase_11 WA -
testcase_12 AC 128 ms
87,296 KB
testcase_13 AC 85 ms
79,732 KB
testcase_14 AC 101 ms
80,384 KB
testcase_15 AC 125 ms
85,376 KB
testcase_16 AC 160 ms
86,992 KB
testcase_17 AC 174 ms
87,168 KB
testcase_18 AC 176 ms
87,296 KB
testcase_19 AC 134 ms
86,656 KB
testcase_20 AC 134 ms
86,784 KB
testcase_21 AC 136 ms
87,168 KB
testcase_22 WA -
testcase_23 WA -
testcase_24 AC 144 ms
87,296 KB
testcase_25 AC 140 ms
87,296 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

sys.setrecursionlimit(20000)

from collections import deque
# a-zに正方向と逆辺を張る
def addEdge(g, a, z):
    g[0][a].append(z)
    g[1][z].append(a)

# グラフの初期化
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))

vCount = n * 2  # 各xとnot x分で2倍
# 0-n-1が各要素のx, n - n*2-1がnot x の 領域

g = []  # グラフ。[0] = 正方向のグラフ。 [1] = 逆方向のグラフ
v = []  # 辺
cmp = []

from pprint import pprint
initGraph(g, edgenum=vCount)

def isDup(a, b, c, d):
    if a < c and b < c:
        return True
    if a > c and b > c:
        return True
    return False

for i in range(n):
    pi = i - 1
    if pi > -1:
        if isDup(dat[i][0], dat[i][1], dat[pi][0], dat[pi][1]) is False:
            addEdge(g, n+i, n+pi)
        if isDup(m - dat[i][0], m-dat[i][1], dat[pi][0], dat[pi][1]) is False:
            addEdge(g, i, n+pi)
        if isDup(dat[i][0], dat[i][1], m-dat[pi][0], m-dat[pi][1]) is False:
            addEdge(g, n+i, pi)
        if isDup(m-dat[i][0], m-dat[i][1], m-dat[pi][0], m-dat[pi][1]) is False:
            addEdge(g, i, pi)

    pi = i + 1
    if pi < n:
        if isDup(dat[i][0], dat[i][1], dat[pi][0], dat[pi][1]) is False:
            addEdge(g, n+i, n+pi)
        if isDup(m - dat[i][0], m-dat[i][1], dat[pi][0], dat[pi][1]) is False:
            addEdge(g, i, n+pi)
        if isDup(dat[i][0], dat[i][1], m-dat[pi][0], m-dat[pi][1]) is False:
            addEdge(g, n+i, pi)
        if isDup(m-dat[i][0], m-dat[i][1], m-dat[pi][0], m-dat[pi][1]) is False:
            addEdge(g, i, pi)

k = scc(g, cmp)
#print(cmp)
f = True
for i in range(n):
    if cmp[i] == cmp[n+i]:
        f = False
        break
print("YES" if f else "NO")
0