結果

問題 No.1576 織姫と彦星
ユーザー irumo8202irumo8202
提出日時 2022-02-16 18:46:52
言語 TypeScript
(5.4.3)
結果
AC  
実行時間 101 ms / 2,000 ms
コード長 1,212 bytes
コンパイル時間 8,912 ms
コンパイル使用メモリ 253,864 KB
実行使用メモリ 45,852 KB
最終ジャッジ日時 2023-09-11 17:13:52
合計ジャッジ時間 17,049 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 74 ms
42,300 KB
testcase_01 AC 75 ms
42,432 KB
testcase_02 AC 75 ms
42,260 KB
testcase_03 AC 75 ms
42,356 KB
testcase_04 AC 74 ms
42,356 KB
testcase_05 AC 75 ms
42,248 KB
testcase_06 AC 74 ms
42,256 KB
testcase_07 AC 89 ms
45,844 KB
testcase_08 AC 87 ms
43,700 KB
testcase_09 AC 76 ms
42,364 KB
testcase_10 AC 94 ms
43,704 KB
testcase_11 AC 76 ms
42,260 KB
testcase_12 AC 91 ms
43,808 KB
testcase_13 AC 93 ms
43,928 KB
testcase_14 AC 94 ms
43,760 KB
testcase_15 AC 94 ms
43,804 KB
testcase_16 AC 93 ms
43,984 KB
testcase_17 AC 92 ms
43,804 KB
testcase_18 AC 90 ms
43,768 KB
testcase_19 AC 90 ms
43,972 KB
testcase_20 AC 79 ms
43,200 KB
testcase_21 AC 98 ms
43,796 KB
testcase_22 AC 88 ms
43,800 KB
testcase_23 AC 80 ms
43,408 KB
testcase_24 AC 89 ms
45,820 KB
testcase_25 AC 93 ms
43,912 KB
testcase_26 AC 90 ms
44,012 KB
testcase_27 AC 79 ms
42,256 KB
testcase_28 AC 92 ms
43,808 KB
testcase_29 AC 90 ms
43,816 KB
testcase_30 AC 76 ms
42,460 KB
testcase_31 AC 89 ms
43,864 KB
testcase_32 AC 91 ms
43,912 KB
testcase_33 AC 100 ms
43,800 KB
testcase_34 AC 76 ms
42,360 KB
testcase_35 AC 91 ms
44,080 KB
testcase_36 AC 88 ms
43,668 KB
testcase_37 AC 100 ms
43,876 KB
testcase_38 AC 93 ms
43,920 KB
testcase_39 AC 91 ms
43,988 KB
testcase_40 AC 89 ms
43,800 KB
testcase_41 AC 90 ms
43,812 KB
testcase_42 AC 79 ms
43,384 KB
testcase_43 AC 89 ms
43,640 KB
testcase_44 AC 101 ms
43,976 KB
testcase_45 AC 88 ms
43,980 KB
testcase_46 AC 96 ms
43,908 KB
testcase_47 AC 80 ms
43,396 KB
testcase_48 AC 92 ms
43,968 KB
testcase_49 AC 92 ms
43,808 KB
testcase_50 AC 77 ms
42,480 KB
testcase_51 AC 81 ms
43,372 KB
testcase_52 AC 90 ms
43,852 KB
testcase_53 AC 95 ms
43,712 KB
testcase_54 AC 93 ms
45,852 KB
testcase_55 AC 92 ms
43,728 KB
testcase_56 AC 92 ms
43,980 KB
testcase_57 AC 76 ms
42,260 KB
testcase_58 AC 89 ms
43,804 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import * as fs from "fs"

const bitCount = (n: number): number => {
    n = n - ((n >>> 1) & 0x55555555)
    n = (n & 0x33333333) + ((n >>> 2) & 0x33333333)
    n = (n + (n >>> 4)) & 0x0f0f0f0f
    n = n + (n >>> 8)
    n = n + (n >>> 16)
    return n & 0x3f
}

const calcDist = (a: number, b: number): number => {
    return bitCount(a ^ b)
}

const bfs = (n: number, arr: number[]): number => {
    const que: number[] = [0]
    const dist = Array(n).fill(-1)
    dist[0] = 0

    while (que.length !== 0) {
        const v = que.shift()
        for (let u = 0; u < n; u++) {
            if (dist[u] !== -1) continue
            if (calcDist(arr[v], arr[u]) !== 1) continue
            dist[u] = dist[v] + 1
            que.push(u)
        }
    }
    return dist[n - 1]
}

const main = (args: string): void => {
    const input = args.trim().split("\n");
    const N = +input.shift()
    const [start, end] = input.shift().split(" ").map(x => Number(x))
    let stones = [start]
    stones = stones.concat(input.shift().split(" ").map(x => Number(x)))
    stones.push(end)

    const ans: number = bfs(N + 2, stones);
    console.log(ans === -1 ? ans : ans - 1)
}

main(fs.readFileSync('/dev/stdin', 'utf8'));
0