結果
問題 | No.1244 Black Segment |
ユーザー |
![]() |
提出日時 | 2021-02-12 20:04:47 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 225 ms / 2,000 ms |
コード長 | 797 bytes |
コンパイル時間 | 281 ms |
コンパイル使用メモリ | 82,560 KB |
実行使用メモリ | 97,408 KB |
最終ジャッジ日時 | 2024-07-19 18:55:29 |
合計ジャッジ時間 | 7,595 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
from collections import dequeimport sysinput = sys.stdin.buffer.readlinesys.setrecursionlimit(10 ** 7)inf = 10**9N, M, A, B = map(int, input().split())source = 0sink = N + 2G = [[] for _ in range(N + 3)]for _ in range(M):L, R = map(int, input().split())R += 1G[L].append((R, 1))G[R].append((L, 1))for i in range(1, A + 1):G[source].append((i, 0))for i in range(B + 1, N + 2):G[i].append((sink, 0))d = [inf] * (N + 3)d[source] = 0q = deque([source])while q:s = q.popleft()ds = d[s]for t, dt in G[s]:if d[t] >= inf:if dt == 0:d[t] = dsq.appendleft(t)else:d[t] = ds + dtq.append(t)ans = d[sink]if ans >= inf:ans = -1print(ans)