結果

問題 No.2674 k-Walk on Bipartite
ユーザー gew1fw
提出日時 2025-06-12 16:23:46
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,496 bytes
コンパイル時間 179 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 148,144 KB
最終ジャッジ日時 2025-06-12 16:24:42
合計ジャッジ時間 7,866 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30 WA * 6
権限があれば一括ダウンロードができます

ソースコード

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

    edges = [[] for _ in range(N+1)]
    for _ in range(M):
        a = int(input[ptr])
        ptr += 1
        b = int(input[ptr])
        ptr += 1
        edges[a].append(b)
        edges[b].append(a)

    color = [-1] * (N + 1)
    component = [0] * (N + 1)
    comp_nodes = []
    comp_edges = []
    current_component = 0

    for u in range(1, N+1):
        if color[u] == -1:
            current_component += 1
            q = deque()
            q.append(u)
            color[u] = 0
            nodes = []
            cnt_edges = 0
            nodes.append(u)
            visited = set()
            visited.add(u)
            while q:
                v = q.popleft()
                for nei in edges[v]:
                    cnt_edges += 1
                    if nei not in visited:
                        color[nei] = color[v] ^ 1
                        visited.add(nei)
                        nodes.append(nei)
                        q.append(nei)
            cnt_edges //= 2
            for node in nodes:
                component[node] = current_component
            comp_nodes.append(len(nodes))
            comp_edges.append(cnt_edges)

    if component[s] != component[t]:
        print("Unknown")
        return

    comp_id = component[s] - 1
    color_s = color[s]
    color_t = color[t]
    if (color_s ^ color_t) != (k % 2):
        print("No")
        return

    # BFS to find distance between s and t
    visited = [False] * (N + 1)
    q = deque()
    q.append((s, 0))
    visited[s] = True
    distance = -1
    while q:
        u, d = q.popleft()
        if u == t:
            distance = d
            break
        for v in edges[u]:
            if not visited[v]:
                visited[v] = True
                q.append((v, d + 1))

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

    if distance > k:
        print("Unknown")
        return

    if (k - distance) % 2 == 0:
        print("Yes")
        return

    nodes_in_comp = comp_nodes[comp_id]
    edges_in_comp = comp_edges[comp_id]
    has_cycle = edges_in_comp >= nodes_in_comp

    if has_cycle:
        print("Yes")
    else:
        print("Unknown")

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