結果

問題 No.274 The Wall
ユーザー prin_kemkemprin_kemkem
提出日時 2023-05-11 21:23:00
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,413 bytes
コンパイル時間 146 ms
コンパイル使用メモリ 82,124 KB
実行使用メモリ 592,968 KB
最終ジャッジ日時 2024-05-05 17:48:37
合計ジャッジ時間 11,982 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 92 ms
79,440 KB
testcase_01 AC 93 ms
79,824 KB
testcase_02 AC 93 ms
79,920 KB
testcase_03 AC 996 ms
361,980 KB
testcase_04 AC 92 ms
79,772 KB
testcase_05 AC 93 ms
79,564 KB
testcase_06 AC 94 ms
80,032 KB
testcase_07 AC 93 ms
80,068 KB
testcase_08 AC 91 ms
79,908 KB
testcase_09 AC 92 ms
80,200 KB
testcase_10 AC 93 ms
79,448 KB
testcase_11 TLE -
testcase_12 AC 151 ms
82,124 KB
testcase_13 AC 115 ms
80,552 KB
testcase_14 AC 159 ms
82,152 KB
testcase_15 AC 198 ms
82,700 KB
testcase_16 AC 1,233 ms
315,464 KB
testcase_17 AC 1,175 ms
316,404 KB
testcase_18 AC 1,243 ms
316,304 KB
testcase_19 AC 230 ms
83,368 KB
testcase_20 AC 240 ms
83,504 KB
testcase_21 AC 236 ms
83,680 KB
testcase_22 AC 247 ms
83,364 KB
testcase_23 AC 242 ms
82,972 KB
testcase_24 AC 249 ms
83,356 KB
testcase_25 AC 252 ms
83,308 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import defaultdict, deque, Counter
import copy
from itertools import combinations, permutations, product, accumulate, groupby
from heapq import heapify, heappop, heappush
import math
import bisect
from pprint import pprint
import sys
# sys.setrecursionlimit(700000)
input = lambda: sys.stdin.readline().rstrip('\n')
inf = float('inf')
mod1 = 10**9+7
mod2 = 998244353
def ceil_div(x, y): return -(-x//y)

#################################################

def sccd(adj):
    n = len(adj)
    been = [False]*n
    P = []
    for s in range(n):
        if been[s]: continue
        stack = [s]
        while stack:
            now = stack.pop()
            if now >= 0:
                if been[now]: continue
                been[now] = True
                stack.append(~now)
                for nxt in adj[now]:
                    if been[nxt]: continue
                    stack.append(nxt)
            else:
                P.append(~now)
    radj = [[] for _ in range(n)]
    for i, neighbor in enumerate(adj):
        for j in neighbor:
            radj[j].append(i)
    scc_prev = []
    scc_idx = [None]*n
    for s in reversed(P):
        if not been[s]: continue
        been[s] = False
        stack = [s]
        scc = []
        while stack:
            now = stack.pop()
            scc_idx[now] = (len(scc_prev), len(scc))
            scc.append(now)
            for nxt in radj[now]:
                if not been[nxt]: continue
                been[nxt] = False
                stack.append(nxt)
        scc_prev.append(scc)
    scc_adj = [None]*len(scc_prev)
    for i, scc in enumerate(scc_prev):
        neighbor = set()
        for now in scc:
            for nxt in adj[now]:
                j = scc_idx[nxt][0]
                if j != i: neighbor.add(j)
        scc_adj[i] = list(neighbor)
    return scc_adj, scc_idx, scc_prev

class Two_SAT:
    def __init__(self, n) -> None:
        self.n = n
        self.adj = [[] for _ in range(2*n)]
    def add(self, x, y): # 否定したいときは~xを入れる
        if x >= 0 and y >= 0:
            self.adj[self.n+x].append(y)
            self.adj[self.n+y].append(x)
        elif x >= 0:
            y = ~y
            self.adj[self.n+x].append(self.n+y)
            self.adj[y].append(x)
        elif y >= 0:
            x = ~x
            self.adj[x].append(y)
            self.adj[self.n+y].append(self.n+x)
        else:
            x = ~x; y = ~y
            self.adj[x].append(self.n+y)
            self.adj[y].append(self.n+x)
    def solve(self):
        _, scc_idx, _ = sccd(self.adj)
        ret = [False]*self.n
        for x in range(self.n):
            i, j = scc_idx[x][0], scc_idx[self.n+x][0]
            if i == j:
                return None
            ret[x] = i > j
        return ret

def is_intersect(li, ri, lj, rj):
    if li > lj: li, ri, lj, rj = ri, rj, li, lj
    return lj <= ri

N, M = map(int, input().split())
blocks = [tuple(map(int, input().split())) for _ in range(N)]
sat = Two_SAT(N)
for i in range(N):
    li, ri = blocks[i]
    for j in range(i+1, N):
        lj, rj = blocks[j]
        if is_intersect(li, ri, lj, rj): sat.add(~i, ~j)
        if is_intersect(li, ri, M-1-rj, M-1-lj): sat.add(~i, j)
        if is_intersect(M-1-ri, M-1-li, lj, rj): sat.add(i, ~j)
        if is_intersect(M-1-ri, M-1-li, M-1-rj, M-1-lj): sat.add(i, j)
ans = sat.solve()
print("YNEOS"[ans is None::2])
0