結果
| 問題 |
No.3072 Speedrun Query
|
| コンテスト | |
| ユーザー |
|
| 提出日時 | 2025-10-04 17:41:50 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 525 ms / 2,500 ms |
| コード長 | 3,315 bytes |
| コンパイル時間 | 328 ms |
| コンパイル使用メモリ | 82,240 KB |
| 実行使用メモリ | 192,120 KB |
| 最終ジャッジ日時 | 2025-10-04 17:42:05 |
| 合計ジャッジ時間 | 14,717 ms |
|
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 21 |
ソースコード
## https://yukicoder.me/problems/no/3072
from collections import deque
MAX_INT = 10 ** 18
def main():
N, Ka, Kb = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
Q = int(input())
st = []
for _ in range(Q):
s, t = map(int, input().split())
st.append((s - 1, t - 1))
# A -> Bを使うパターン
b_set = set([b - 1 for b in B])
array_a = [MAX_INT] * (N + 2)
queue = deque()
array_a[N] = 0
for a in A:
array_a[a - 1] = 0
queue.append(a - 1)
while len(queue) > 0:
x = queue.popleft()
if x < N:
for dx in (-1, 1):
new_x = dx + x
if 0 <= new_x < N:
if array_a[new_x] > array_a[x] + 1:
array_a[new_x] = array_a[x] + 1
queue.append(new_x)
if x in b_set:
if array_a[N + 1] > array_a[x]:
array_a[N + 1] = array_a[x]
queue.appendleft(N + 1)
else:
for b in b_set:
if array_a[b] > array_a[x]:
array_a[b] = array_a[x]
queue.appendleft(b)
# B -> Aを使うパターン
a_set = set([a - 1 for a in A])
array_b = [MAX_INT] * (N + 2)
queue = deque()
array_b[N + 1] = 0
for b in B:
array_b[b - 1] = 0
queue.append(b - 1)
while len(queue) > 0:
x = queue.popleft()
if x < N:
for dx in (-1, 1):
new_x = dx + x
if 0 <= new_x < N:
if array_b[new_x] > array_b[x] + 1:
array_b[new_x] = array_b[x] + 1
queue.append(new_x)
if x in a_set:
if array_b[N] > array_b[x]:
array_b[N] = array_b[x]
queue.appendleft(N)
else:
for a in a_set:
if array_b[a] > array_b[x]:
array_b[a] = array_b[x]
queue.appendleft(a)
# Aに乗るパターン
array_a1 = [MAX_INT] * (N + 2)
queue = deque()
array_a1[N] = 0
for a in A:
array_a1[a - 1] = 0
queue.append(a - 1)
while len(queue) > 0:
x = queue.popleft()
for dx in (-1, 1):
new_x = dx + x
if 0 <= new_x < N:
if array_a1[new_x] > array_a1[x] + 1:
array_a1[new_x] = array_a1[x] + 1
queue.append(new_x)
# Bに乗るパターン
array_b1 = [MAX_INT] * (N + 2)
queue = deque()
array_b1[N + 1] = 0
for b in B:
array_b1[b - 1] = 0
queue.append(b - 1)
while len(queue) > 0:
x = queue.popleft()
for dx in (-1, 1):
new_x = dx + x
if 0 <= new_x < N:
if array_b1[new_x] > array_b1[x] + 1:
array_b1[new_x] = array_b1[x] + 1
queue.append(new_x)
for s, t in st:
answer = abs(s - t)
answer = min(array_a1[s] + array_a[t], answer )
answer = min(array_b1[s] + array_b[t], answer )
print(answer)
if __name__ == "__main__":
main()