結果
問題 |
No.274 The Wall
|
ユーザー |
|
提出日時 | 2021-12-29 07:33:40 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 722 ms / 2,000 ms |
コード長 | 1,662 bytes |
コンパイル時間 | 401 ms |
コンパイル使用メモリ | 12,544 KB |
実行使用メモリ | 11,648 KB |
最終ジャッジ日時 | 2025-03-17 19:11:10 |
合計ジャッジ時間 | 7,769 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 23 |
ソースコード
def scc(N, G, RG): order = [] used = [0]*N group = [None]*N def dfs(s): used[s] = 1 for t in G[s]: if not used[t]: dfs(t) order.append(s) def rdfs(s, col): group[s] = col used[s] = 1 for t in RG[s]: if not used[t]: rdfs(t, col) for i in range(N): if not used[i]: dfs(i) used = [0]*N label = 0 for s in reversed(order): if not used[s]: rdfs(s, label) label += 1 return label, group def main(): N, M = map(int, input().split()) B = [list(map(int, input().split())) for _ in range(N)] g = [[] for _ in range(N*2)] def check(L1, R1, L2, R2, i, j): # AT BT rL1 = M-R1-1 rR1 = M-L1-1 f1 = f2 = False if not (R1 < L2 or R2 < L1): f1 = True if not (rR1 < L2 or R2 < rL1): f2 = True if f1 and f2: return False if f1: g[i].append(j+N) g[i+N].append(j) g[j].append(i+N) g[j+N].append(i) if f2: g[i].append(j) g[i+N].append(j+N) g[j].append(i) g[j+N].append(i+N) return True for i in range(N): L1, R1 = B[i] for j in range(i+1, N): L2, R2 = B[j] if not check(L1, R1, L2, R2, i, j): print("NO") return _, nums = scc(N*2, g, g) for i in range(N): if nums[i] == nums[i+N]: print("NO") return print("YES") main()