結果

問題 No.1576 織姫と彦星
ユーザー ntuda
提出日時 2021-09-07 22:14:21
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 65 ms / 2,000 ms
コード長 695 bytes
コンパイル時間 958 ms
コンパイル使用メモリ 81,792 KB
実行使用メモリ 62,848 KB
最終ジャッジ日時 2024-12-24 00:25:08
合計ジャッジ時間 5,814 ms
ジャッジサーバーID
(参考情報)
judge3 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 5
other AC * 54
権限があれば一括ダウンロードができます

ソースコード

diff #

import sys

N = int(input())
start,end = map(int,input().split())
S = list(map(int,input().split()))
S = [start] + S + [end]
E = [[] for _ in range(N+2)]
A = [pow(2,i) for i in range(30)]
A.append(0)
A = set(A)

for i in range(N+1):
    for j in range(i+1,N+2):
        if S[i] ^ S[j] in A:
            E[i].append(j)
            E[j].append(i)

visited = [0] * (N+2)
que1 = {0}
que2 = set()
visited[0] = 1
cnt = 0
while que1:
    for q in que1:
        if q == N+1:
            print(cnt-1)
            sys.exit()
        for e in E[q]:
            if visited[e] != 1:
                visited[e] = 1
                que2.add(e)
    que1,que2 = que2,que1
    que2.clear()
    cnt += 1
print(-1)
0