結果

問題 No.1400 すごろくで世界旅行
ユーザー gew1fw
提出日時 2025-06-12 18:53:13
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,583 bytes
コンパイル時間 317 ms
コンパイル使用メモリ 82,268 KB
実行使用メモリ 96,148 KB
最終ジャッジ日時 2025-06-12 18:53:33
合計ジャッジ時間 13,966 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17 WA * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    V = int(input[idx])
    D = int(input[idx + 1])
    idx += 2
    E = input[idx:idx + V]
    idx += V

    # Precompute adjacency masks
    mask = [0] * V
    for i in range(V):
        for j in range(V):
            if E[i][j] == '1':
                mask[i] |= 1 << j

    # Check connectivity using BFS with bitmask
    visited = 0
    queue = 1 << 0
    visited |= queue
    while queue:
        current = queue
        queue = 0
        bits = current
        while bits:
            lsb = bits & -bits
            bit_pos = (lsb).bit_length() - 1
            bits ^= lsb
            neighbors = mask[bit_pos]
            new_neighbors = neighbors & ~visited
            visited |= new_neighbors
            queue |= new_neighbors
    if visited != (1 << V) - 1:
        print("No")
        return

    # Check bipartiteness using BFS
    color = [-1] * V
    is_bipart = True
    for i in range(V):
        if color[i] == -1:
            color[i] = 0
            q = [i]
            ptr = 0
            while ptr < len(q):
                u = q[ptr]
                ptr += 1
                for v in range(V):
                    if E[u][v] == '1':
                        if color[v] == -1:
                            color[v] = color[u] ^ 1
                            q.append(v)
                        elif color[v] == color[u]:
                            is_bipart = False
                            break
                if not is_bipart:
                    break
            if not is_bipart:
                break

    # Compute the maximum shortest path (diameter)
    max_dist = 0
    for i in range(V):
        current_visited = 0
        current_queue = 1 << i
        current_visited |= current_queue
        dist = 0
        local_max = 0
        while current_queue:
            next_queue = 0
            bits = current_queue
            while bits:
                lsb = bits & -bits
                bit_pos = (lsb).bit_length() - 1
                bits ^= lsb
                next_queue |= mask[bit_pos]
            next_queue &= ~current_visited
            if next_queue:
                dist += 1
                local_max = dist
            current_visited |= next_queue
            current_queue = next_queue
        if local_max > max_dist:
            max_dist = local_max

    if not is_bipart:
        print("Yes" if D >= max_dist else "No")
    else:
        print("Yes" if D >= max_dist and (D - max_dist) % 2 == 0 else "No")

if __name__ == "__main__":
    main()
0