結果
問題 |
No.1576 織姫と彦星
|
ユーザー |
|
提出日時 | 2021-12-09 23:01:04 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 89 ms / 2,000 ms |
コード長 | 795 bytes |
コンパイル時間 | 203 ms |
コンパイル使用メモリ | 82,128 KB |
実行使用メモリ | 69,760 KB |
最終ジャッジ日時 | 2024-07-17 15:56:39 |
合計ジャッジ時間 | 5,703 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 54 |
ソースコード
from collections import defaultdict, deque n = int(input()) s, e = map(int, input().split()) A = list(map(int, input().split())) A = [s] + A + [e] nei_dict = defaultdict(list) for i in range(n + 1): for j in range(i + 1, n + 2): num = A[i] ^ A[j] cnt = 0 while num != 0: if num % 2 == 1: cnt += 1 if cnt == 2: break num //= 2 if cnt == 1: nei_dict[i].append(j) nei_dict[j].append(i) seen = set([0]) dq = deque([(0, 1)]) while dq: curr, cnt = dq.popleft() if curr == n + 1: print(cnt - 2) exit() for np in nei_dict[curr]: if np in seen: continue seen.add(np) dq.append((np, cnt + 1)) print(-1)