結果

問題 No.274 The Wall
ユーザー tjaketjake
提出日時 2020-10-18 21:08:52
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
AC  
実行時間 556 ms / 2,000 ms
コード長 1,979 bytes
コンパイル時間 155 ms
コンパイル使用メモリ 12,800 KB
実行使用メモリ 12,288 KB
最終ジャッジ日時 2024-07-21 06:45:10
合計ジャッジ時間 5,672 ms
ジャッジサーバーID
(参考情報)
judge1 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 4
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import sys
from collections import deque
readline = sys.stdin.readline
write = sys.stdout.write
sys.setrecursionlimit(10**5)
def scc(N, G, RG):
order = []
used = [0]*N
def dfs(s):
used[s] = 1
for t in G[s]:
if not used[t]:
dfs(t)
order.append(s)
for i in range(N):
if not used[i]:
dfs(i)
group = [-1]*N
label = 0
order.reverse()
for s in order:
if group[s] != -1:
continue
que = deque([s])
group[s] = label
while que:
v = que.popleft()
for w in RG[v]:
if group[w] != -1:
continue
que.append(w)
group[w] = label
label += 1
return label, group
def solve():
N, M = map(int, readline().split())
S = [tuple(map(int, readline().split())) for i in range(N)]
G = [[] for i in range(2*N)]
RG = [[] for i in range(2*N)]
def add_edge(i, neg_i, j, neg_j):
if neg_i:
i0 = i+N; i1 = i
else:
i0 = i; i1 = i+N
if neg_j:
j0 = j+N; j1 = j
else:
j0 = j; j1 = j+N
G[i1].append(j0); RG[j0].append(i1)
G[j1].append(i0); RG[i0].append(j1)
for i in range(N):
li, ri = S[i]
for j in range(i+1, N):
lj, rj = S[j]
p = q = 0
if (li <= rj and lj <= ri):
add_edge(i, 0, j, 0)
add_edge(i, 1, j, 1)
p = 1
if (li <= M-1-lj and M-1-rj <= ri):
add_edge(i, 0, j, 1)
add_edge(i, 1, j, 0)
q = 1
if p and q:
write("NO\n")
return
_, group = scc(2*N, G, RG)
ok = 1
for i in range(N):
if group[i] == group[i+N]:
ok = 0
break
if ok:
write("YES\n")
else:
write("NO\n")
solve()
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0