結果

問題 No.2674 k-Walk on Bipartite
コンテスト
ユーザー lam6er
提出日時 2025-04-16 16:03:22
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,474 bytes
コンパイル時間 233 ms
コンパイル使用メモリ 81,680 KB
実行使用メモリ 131,856 KB
最終ジャッジ日時 2025-04-16 16:09:55
合計ジャッジ時間 7,066 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 32 WA * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

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

    adj = [[] for _ in range(N+1)]
    edges = []
    for _ in range(M):
        u = int(input[ptr])
        ptr += 1
        v = int(input[ptr])
        ptr += 1
        adj[u].append(v)
        adj[v].append(u)
        edges.append((u, v))

    # Find connected components
    visited = [False] * (N + 1)
    components = []
    component_id = [0] * (N + 1)
    current_id = 0

    for node in range(1, N + 1):
        if not visited[node]:
            q = deque()
            q.append(node)
            visited[node] = True
            component = []
            while q:
                u = q.popleft()
                component.append(u)
                for v in adj[u]:
                    if not visited[v]:
                        visited[v] = True
                        q.append(v)
            components.append(component)
            for u in component:
                component_id[u] = current_id
            current_id += 1

    # Compute edge counts for each component
    component_edge_counts = [0] * len(components)
    for u, v in edges:
        if component_id[u] == component_id[v]:
            component_edge_counts[component_id[u]] += 1

    if s == t:
        if k % 2 != 0:
            print("No")
        else:
            comp_id = component_id[s]
            if component_edge_counts[comp_id] >= 1:
                print("Yes")
            else:
                print("No")
        return

    # Check if s and t are in the same component
    if component_id[s] != component_id[t]:
        print("Unknown")
        return

    # BFS to find shortest path from s to t
    visited_bfs = [False] * (N + 1)
    q = deque()
    q.append((s, 0))
    visited_bfs[s] = True
    d = -1
    while q:
        u, dist = q.popleft()
        if u == t:
            d = dist
            break
        for v in adj[u]:
            if not visited_bfs[v]:
                visited_bfs[v] = True
                q.append((v, dist + 1))

    if d == -1:
        print("Unknown")
        return

    if (d % 2) != (k % 2):
        print("No")
    else:
        if k >= d:
            print("Yes")
        else:
            print("Unknown")

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