結果

問題 No.274 The Wall
ユーザー recuraki
提出日時 2020-02-04 12:53:19
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 309 ms / 2,000 ms
コード長 4,449 bytes
コンパイル時間 137 ms
コンパイル使用メモリ 82,072 KB
実行使用メモリ 88,396 KB
最終ジャッジ日時 2024-06-22 02:35:03
合計ジャッジ時間 4,985 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

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")
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0