結果
| 問題 | No.274 The Wall |
| ユーザー |
 zkou
|
| 提出日時 | 2021-03-12 19:32:56 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 163 ms / 2,000 ms |
| コード長 | 6,440 bytes |
| コンパイル時間 | 164 ms |
| コンパイル使用メモリ | 81,920 KB |
| 実行使用メモリ | 77,344 KB |
| 最終ジャッジ日時 | 2024-10-14 09:45:17 |
| 合計ジャッジ時間 | 3,091 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge3 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 41 ms
52,992 KB |
| testcase_01 | AC | 40 ms
52,352 KB |
| testcase_02 | AC | 40 ms
52,736 KB |
| testcase_03 | AC | 46 ms
60,800 KB |
| testcase_04 | AC | 40 ms
52,864 KB |
| testcase_05 | AC | 40 ms
52,736 KB |
| testcase_06 | AC | 40 ms
53,248 KB |
| testcase_07 | AC | 40 ms
52,736 KB |
| testcase_08 | AC | 40 ms
52,736 KB |
| testcase_09 | AC | 40 ms
52,480 KB |
| testcase_10 | AC | 40 ms
52,736 KB |
| testcase_11 | AC | 47 ms
61,696 KB |
| testcase_12 | AC | 75 ms
68,480 KB |
| testcase_13 | AC | 55 ms
62,976 KB |
| testcase_14 | AC | 100 ms
76,344 KB |
| testcase_15 | AC | 125 ms
76,672 KB |
| testcase_16 | AC | 47 ms
61,528 KB |
| testcase_17 | AC | 46 ms
61,696 KB |
| testcase_18 | AC | 45 ms
61,824 KB |
| testcase_19 | AC | 147 ms
77,176 KB |
| testcase_20 | AC | 158 ms
76,892 KB |
| testcase_21 | AC | 155 ms
77,328 KB |
| testcase_22 | AC | 157 ms
77,320 KB |
| testcase_23 | AC | 159 ms
77,344 KB |
| testcase_24 | AC | 163 ms
77,052 KB |
| testcase_25 | AC | 162 ms
77,196 KB |
ソースコード
class _csr:
def __init__(self, n, edges):
self.start = [0] * (n + 1)
self.elist = [0] * len(edges)
for v, _ in edges:
self.start[v + 1] += 1
for i in range(1, n + 1):
self.start[i] += self.start[i - 1]
counter = self.start.copy()
for v, e in edges:
self.elist[counter[v]] = e
counter[v] += 1
class scc_graph:
"""It calculates the strongly connected components of directed graphs.
"""
def __init__(self, n):
"""It creates a directed graph with n vertices and 0 edges.
Constraints
-----------
> 0 <= n <= 10 ** 8
Complexity
----------
> O(n)
"""
self.n = n
self.edges = []
def add_edge(self, from_, to):
"""It adds a directed edge from the vertex `from_` to the vertex `to`.
Constraints
-----------
> 0 <= from_ < n
> 0 <= to < n
Complexity
----------
> O(1) amortized
"""
assert 0 <= from_ < self.n
assert 0 <= to < self.n
self.edges.append((from_, to))
def _scc_ids(self):
g = _csr(self.n, self.edges)
now_ord = 0
group_num = 0
visited = []
low = [0] * self.n
order = [-1] * self.n
ids = [0] * self.n
parent = [-1] * self.n
stack = []
for i in range(self.n):
if order[i] == -1:
stack.append(i)
stack.append(i)
while stack:
v = stack.pop()
if order[v] == -1:
low[v] = order[v] = now_ord
now_ord += 1
visited.append(v)
for i in range(g.start[v], g.start[v + 1]):
to = g.elist[i]
if order[to] == -1:
stack.append(to)
stack.append(to)
parent[to] = v
else:
low[v] = min(low[v], order[to])
else:
if low[v] == order[v]:
while True:
u = visited.pop()
order[u] = self.n
ids[u] = group_num
if u == v:
break
group_num += 1
if parent[v] != -1:
low[parent[v]] = min(low[parent[v]], low[v])
for i, x in enumerate(ids):
ids[i] = group_num - 1 - x
return group_num, ids
def scc(self):
"""It returns the list of the "list of the vertices" that satisfies the following.
> Each vertex is in exactly one "list of the vertices".
> Each "list of the vertices" corresponds to the vertex set of a strongly connected component.
The order of the vertices in the list is undefined.
> The list of "list of the vertices" are sorted in topological order,
i.e., for two vertices u, v in different strongly connected components,
if there is a directed path from u to v,
the list contains u appears earlier than the list contains v.
Complexity
----------
> O(n + m), where m is the number of added edges.
"""
group_num, ids = self._scc_ids()
groups = [[] for _ in range(group_num)]
for i, x in enumerate(ids):
groups[x].append(i)
return groups
class two_sat:
"""It solves 2-SAT.
For variables x[0], x[1], ..., x[n-1] and clauses with form
> ((x[i] = f) or (x[j] = g)),
it decides whether there is a truth assignment that satisfies all clauses.
"""
def __init__(self, n):
"""It creates a 2-SAT of n variables and 0 clauses.
Constraints
-----------
> 0 <= n <= 10 ** 8
Complexity
----------
> O(n)
"""
self.n = n
self._answer = [False] * n
self.scc = scc_graph(2 * n)
def add_clause(self, i, f, j, g):
"""It adds a clause ((x[i] = f) or (x[j] = g)).
Constraints
-----------
> 0 <= i < n
> 0 <= j < n
Complexity
----------
> O(1) amortized
"""
assert 0 <= i < self.n
assert 0 <= j < self.n
self.scc.add_edge(2 * i + (f == 0), 2 * j + (g == 1))
self.scc.add_edge(2 * j + (g == 0), 2 * i + (f == 1))
def satisfiable(self):
"""If there is a truth assignment that satisfies all clauses, it returns `True`.
Otherwise, it returns `False`.
Constraints
-----------
> You may call it multiple times.
Complexity
----------
> O(n + m), where m is the number of added clauses.
"""
_, ids = self.scc._scc_ids()
for i in range(self.n):
if ids[2 * i] == ids[2 * i + 1]:
return False
self._answer[i] = (ids[2*i] < ids[2*i+1])
return True
def answer(self):
"""It returns a truth assignment that satisfies all clauses of the last call of `satisfiable`.
If we call it before calling `satisfiable` or when the last call of `satisfiable` returns `False`,
it returns the list of length n with undefined elements.
Complexity
----------
> O(n)
"""
return self._answer.copy()
def main():
import sys
input = sys.stdin.buffer.readline
N, M = map(int, input().split())
LRs = [tuple(map(int, input().split())) for _ in range(N)]
ts = two_sat(N)
for i in range(N):
Li, Ri = LRs[i]
for j in range(i + 1, N):
Lj, Rj = LRs[j]
f1 = not (Ri < Lj or Rj < Li)
f2 = not (M - 1 - Li < Lj or Rj < M - 1 - Ri)
if f1 and f2:
print("NO")
exit()
if f1:
ts.add_clause(i, 0, j, 0)
ts.add_clause(i, 1, j, 1)
if f2:
ts.add_clause(i, 0, j, 1)
ts.add_clause(i, 1, j, 0)
print("YES" if ts.satisfiable() else "NO")
main()