結果

問題 No.2674 k-Walk on Bipartite
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 14:38:33
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,375 bytes
コンパイル時間 343 ms
コンパイル使用メモリ 82,252 KB
実行使用メモリ 125,224 KB
最終ジャッジ日時 2025-06-12 14:38:42
合計ジャッジ時間 5,167 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30 WA * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def main():
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx]); idx +=1
    M = int(input[idx]); idx +=1
    s = int(input[idx]); idx +=1
    t = int(input[idx]); idx +=1
    k = int(input[idx]); idx +=1

    if s == t:
        if k % 2 == 0:
            print("Yes")
        else:
            print("No")
        return

    # Build adjacency list
    adj = [[] for _ in range(N+1)]  # 1-based
    for _ in range(M):
        a = int(input[idx]); idx +=1
        b = int(input[idx]); idx +=1
        adj[a].append(b)
        adj[b].append(a)

    # BFS to find distance and check if t is reachable
    visited = [False] * (N+1)
    distance = [-1] * (N+1)
    q = deque()
    q.append(s)
    visited[s] = True
    distance[s] = 0

    while q:
        u = q.popleft()
        for v in adj[u]:
            if not visited[v]:
                visited[v] = True
                distance[v] = distance[u] + 1
                q.append(v)
                if v == t:
                    break  # early exit if found

    if not visited[t]:
        print("Unknown")
        return

    d = distance[t]
    required_parity = d % 2
    if (k % 2) != required_parity:
        print("No")
    else:
        if d <= k:
            print("Yes")
        else:
            print("Unknown")

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