結果

問題 No.3072 Speedrun Query
ユーザー LyricalMaestro
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

## 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()
0