結果
問題 | No.274 The Wall |
ユーザー | prin_kemkem |
提出日時 | 2023-05-11 21:47:06 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 3,247 bytes |
コンパイル時間 | 170 ms |
コンパイル使用メモリ | 82,036 KB |
実行使用メモリ | 794,972 KB |
最終ジャッジ日時 | 2024-05-05 18:02:57 |
合計ジャッジ時間 | 11,884 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 99 ms
80,000 KB |
testcase_01 | AC | 96 ms
80,128 KB |
testcase_02 | AC | 95 ms
80,128 KB |
testcase_03 | AC | 951 ms
391,588 KB |
testcase_04 | AC | 88 ms
79,920 KB |
testcase_05 | AC | 88 ms
79,616 KB |
testcase_06 | AC | 88 ms
79,616 KB |
testcase_07 | AC | 91 ms
79,872 KB |
testcase_08 | AC | 91 ms
79,640 KB |
testcase_09 | AC | 91 ms
80,000 KB |
testcase_10 | AC | 91 ms
79,744 KB |
testcase_11 | TLE | - |
testcase_12 | AC | 144 ms
81,280 KB |
testcase_13 | AC | 112 ms
80,704 KB |
testcase_14 | AC | 140 ms
82,028 KB |
testcase_15 | AC | 172 ms
82,528 KB |
testcase_16 | AC | 1,227 ms
417,172 KB |
testcase_17 | AC | 1,130 ms
368,432 KB |
testcase_18 | AC | 1,286 ms
414,364 KB |
testcase_19 | AC | 209 ms
82,288 KB |
testcase_20 | AC | 206 ms
83,052 KB |
testcase_21 | AC | 202 ms
82,488 KB |
testcase_22 | AC | 211 ms
83,212 KB |
testcase_23 | AC | 208 ms
83,336 KB |
testcase_24 | AC | 210 ms
83,344 KB |
testcase_25 | AC | 212 ms
83,224 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])