結果
問題 | No.274 The Wall |
ユーザー |
![]() |
提出日時 | 2020-10-18 21:08:52 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 521 ms / 2,000 ms |
コード長 | 1,979 bytes |
コンパイル時間 | 262 ms |
コンパイル使用メモリ | 12,544 KB |
実行使用メモリ | 12,032 KB |
最終ジャッジ日時 | 2025-03-17 19:08:41 |
合計ジャッジ時間 | 5,779 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 23 |
ソースコード
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()