結果
問題 | No.274 The Wall |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
import sysfrom collections import dequereadline = sys.stdin.readlinewrite = sys.stdout.writesys.setrecursionlimit(10**5)def scc(N, G, RG):order = []used = [0]*Ndef dfs(s):used[s] = 1for 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]*Nlabel = 0order.reverse()for s in order:if group[s] != -1:continueque = deque([s])group[s] = labelwhile que:v = que.popleft()for w in RG[v]:if group[w] != -1:continueque.append(w)group[w] = labellabel += 1return label, groupdef 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 = ielse:i0 = i; i1 = i+Nif neg_j:j0 = j+N; j1 = jelse:j0 = j; j1 = j+NG[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 = 0if (li <= rj and lj <= ri):add_edge(i, 0, j, 0)add_edge(i, 1, j, 1)p = 1if (li <= M-1-lj and M-1-rj <= ri):add_edge(i, 0, j, 1)add_edge(i, 1, j, 0)q = 1if p and q:write("NO\n")return_, group = scc(2*N, G, RG)ok = 1for i in range(N):if group[i] == group[i+N]:ok = 0breakif ok:write("YES\n")else:write("NO\n")solve()