結果
問題 | No.274 The Wall |
ユーザー | prin_kemkem |
提出日時 | 2023-05-11 21:37:02 |
言語 | PyPy3 (7.3.15) |
結果 |
MLE
|
実行時間 | - |
コード長 | 3,055 bytes |
コンパイル時間 | 953 ms |
コンパイル使用メモリ | 87,048 KB |
実行使用メモリ | 613,408 KB |
最終ジャッジ日時 | 2023-08-18 12:38:34 |
合計ジャッジ時間 | 7,786 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 143 ms
78,660 KB |
testcase_01 | AC | 144 ms
78,604 KB |
testcase_02 | AC | 142 ms
78,640 KB |
testcase_03 | AC | 1,007 ms
350,816 KB |
testcase_04 | AC | 321 ms
78,700 KB |
testcase_05 | AC | 141 ms
78,696 KB |
testcase_06 | AC | 139 ms
78,228 KB |
testcase_07 | AC | 141 ms
78,548 KB |
testcase_08 | AC | 141 ms
78,452 KB |
testcase_09 | AC | 146 ms
78,528 KB |
testcase_10 | AC | 138 ms
78,560 KB |
testcase_11 | MLE | - |
testcase_12 | AC | 713 ms
82,716 KB |
testcase_13 | AC | 162 ms
81,380 KB |
testcase_14 | AC | 200 ms
82,664 KB |
testcase_15 | AC | 243 ms
83,276 KB |
testcase_16 | AC | 1,207 ms
328,192 KB |
testcase_17 | AC | 1,167 ms
299,916 KB |
testcase_18 | AC | 1,249 ms
323,424 KB |
testcase_19 | AC | 265 ms
83,148 KB |
testcase_20 | AC | 276 ms
84,176 KB |
testcase_21 | AC | 268 ms
83,736 KB |
testcase_22 | AC | 274 ms
84,164 KB |
testcase_23 | AC | 278 ms
84,220 KB |
testcase_24 | AC | 270 ms
84,504 KB |
testcase_25 | AC | 279 ms
84,264 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): 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 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)] 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], scc_idx[self.n+x] 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) del blocks ans = sat.solve() print("YNEOS"[ans is None::2])