結果

問題 No.2674 k-Walk on Bipartite
ユーザー qwer1234qwer
提出日時 2025-03-19 18:19:55
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,715 bytes
コンパイル時間 367 ms
コンパイル使用メモリ 82,244 KB
実行使用メモリ 146,796 KB
最終ジャッジ日時 2025-03-19 18:20:04
合計ジャッジ時間 7,960 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30 WA * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def main():
    sys.setrecursionlimit(1 << 25)
    input = sys.stdin.read
    data = input().split()
    idx = 0
    N = int(data[idx]); idx +=1
    M = int(data[idx]); idx +=1
    s = int(data[idx])-1; idx +=1
    t = int(data[idx])-1; idx +=1
    k = int(data[idx]); idx +=1
    edges = [[] for _ in range(N)]
    for __ in range(M):
        a = int(data[idx])-1; idx +=1
        b = int(data[idx])-1; idx +=1
        edges[a].append(b)
        edges[b].append(a)
    
    # BFS to find connected components and distances
    visited = [-1] * N
    components = []
    edges_count = []
    all_component_edges = 0
    for i in range(N):
        if visited[i] == -1:
            q = deque()
            q.append(i)
            visited[i] = len(components)
            component = [i]
            comp_edges = 0
            while q:
                u = q.popleft()
                for v in edges[u]:
                    if visited[v] == -1:
                        visited[v] = len(components)
                        q.append(v)
                        component.append(v)
            components.append(component)
            # Now, count edges within this component
            comp_set = set(component)
            e_count = 0
            for u in component:
                for v in edges[u]:
                    if v in comp_set and u < v:
                        e_count +=1
            edges_count.append(e_count)
    cs = visited[s]
    ct = visited[t]
    
    # Check if in the same component
    if cs == ct:
        # Compute shortest distance d in this component
        comp = components[cs]
        dist = [-1] * N
        q = deque()
        q.append(s)
        dist[s] = 0
        found = False
        while q and not found:
            u = q.popleft()
            for v in edges[u]:
                if dist[v] == -1:
                    dist[v] = dist[u] + 1
                    if v == t:
                        found = True
                        break
                    q.append(v)
        d = dist[t]
        if (d % 2) != (k % 2):
            print("No")
            return
        # Now, determine if in this component, E >= V?
        V = len(components[cs])
        E = edges_count[cs]
        if E >= V:
            print("Yes")
            return
        else:
            if d <= k:
                print("Yes")
            else:
                print("Unknown")
    else:
        # Check if parity can be adjusted
        # s and t are in different components. Since their components can be independently flipped, parity can always be matched.
        # So step 1 passed
        print("Unknown")
    
if __name__ == '__main__':
    main()
0