結果
問題 | No.274 The Wall |
ユーザー | prin_kemkem |
提出日時 | 2023-05-11 21:47:06 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 3,247 bytes |
コンパイル時間 | 570 ms |
コンパイル使用メモリ | 86,784 KB |
実行使用メモリ | 808,328 KB |
最終ジャッジ日時 | 2023-08-18 12:45:24 |
合計ジャッジ時間 | 12,656 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 143 ms
78,400 KB |
testcase_01 | AC | 145 ms
78,540 KB |
testcase_02 | AC | 143 ms
78,388 KB |
testcase_03 | AC | 985 ms
393,448 KB |
testcase_04 | AC | 141 ms
78,336 KB |
testcase_05 | AC | 142 ms
78,472 KB |
testcase_06 | AC | 143 ms
78,392 KB |
testcase_07 | AC | 140 ms
78,192 KB |
testcase_08 | AC | 140 ms
78,472 KB |
testcase_09 | AC | 141 ms
78,340 KB |
testcase_10 | AC | 141 ms
78,388 KB |
testcase_11 | TLE | - |
testcase_12 | AC | 190 ms
82,052 KB |
testcase_13 | AC | 165 ms
81,136 KB |
testcase_14 | AC | 200 ms
82,740 KB |
testcase_15 | AC | 220 ms
82,692 KB |
testcase_16 | AC | 1,247 ms
414,836 KB |
testcase_17 | AC | 1,212 ms
370,936 KB |
testcase_18 | AC | 1,285 ms
415,456 KB |
testcase_19 | AC | 253 ms
83,684 KB |
testcase_20 | AC | 264 ms
83,384 KB |
testcase_21 | AC | 252 ms
83,460 KB |
testcase_22 | AC | 265 ms
83,740 KB |
testcase_23 | AC | 260 ms
83,372 KB |
testcase_24 | AC | 270 ms
83,352 KB |
testcase_25 | AC | 266 ms
84,140 KB |
ソースコード
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, radj): 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) scc_idx = [None]*n idx = 0 for s in reversed(P): if not been[s]: continue been[s] = False stack = [s] while stack: now = stack.pop() scc_idx[now] = idx for nxt in radj[now]: if not been[nxt]: continue been[nxt] = False stack.append(nxt) idx += 1 return scc_idx class Two_SAT: def __init__(self, n) -> None: self.n = n self.adj = [[] for _ in range(2*n)] self.radj = [[] 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.radj[y].append(self.n+x) self.adj[self.n+y].append(x) self.radj[x].append(self.n+y) elif x >= 0: y = ~y self.adj[self.n+x].append(self.n+y) self.radj[self.n+y].append(self.n+x) self.adj[y].append(x) self.radj[x].append(y) elif y >= 0: x = ~x self.adj[x].append(y) self.radj[y].append(x) self.adj[self.n+y].append(self.n+x) self.radj[self.n+x].append(self.n+y) else: x = ~x; y = ~y self.adj[x].append(self.n+y) self.radj[self.n+y].append(x) self.adj[y].append(self.n+x) self.radj[self.n+x].append(y) def solve(self): scc_idx = sccd(self.adj, self.radj) for x in range(self.n): i, j = scc_idx[x], scc_idx[self.n+x] if i == j: return None return 0 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) del blocks ans = sat.solve() print("YNEOS"[ans is None::2])