結果
問題 | No.274 The Wall |
ユーザー | prin_kemkem |
提出日時 | 2023-05-11 21:23:00 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 3,413 bytes |
コンパイル時間 | 427 ms |
コンパイル使用メモリ | 87,048 KB |
実行使用メモリ | 609,380 KB |
最終ジャッジ日時 | 2023-08-18 12:28:33 |
合計ジャッジ時間 | 14,292 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 140 ms
78,576 KB |
testcase_01 | AC | 141 ms
78,640 KB |
testcase_02 | AC | 139 ms
78,632 KB |
testcase_03 | AC | 935 ms
330,976 KB |
testcase_04 | AC | 134 ms
78,440 KB |
testcase_05 | AC | 134 ms
78,652 KB |
testcase_06 | AC | 138 ms
78,672 KB |
testcase_07 | AC | 140 ms
78,300 KB |
testcase_08 | AC | 138 ms
78,444 KB |
testcase_09 | AC | 140 ms
78,312 KB |
testcase_10 | AC | 140 ms
78,632 KB |
testcase_11 | TLE | - |
testcase_12 | AC | 277 ms
82,888 KB |
testcase_13 | AC | 164 ms
81,260 KB |
testcase_14 | AC | 208 ms
82,972 KB |
testcase_15 | AC | 230 ms
83,508 KB |
testcase_16 | AC | 1,290 ms
328,280 KB |
testcase_17 | AC | 1,156 ms
300,648 KB |
testcase_18 | AC | 1,254 ms
323,412 KB |
testcase_19 | AC | 269 ms
84,592 KB |
testcase_20 | AC | 281 ms
84,592 KB |
testcase_21 | AC | 279 ms
84,760 KB |
testcase_22 | AC | 284 ms
84,700 KB |
testcase_23 | AC | 286 ms
84,588 KB |
testcase_24 | AC | 285 ms
84,596 KB |
testcase_25 | AC | 287 ms
84,956 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 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])