結果

問題 No.2948 move move rotti
コンテスト
ユーザー lam6er
提出日時 2025-03-20 21:19:57
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,799 ms / 4,000 ms
コード長 1,902 bytes
コンパイル時間 192 ms
コンパイル使用メモリ 82,696 KB
実行使用メモリ 245,608 KB
最終ジャッジ日時 2025-03-20 21:21:05
合計ジャッジ時間 13,222 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def main():
    n, m, k = map(int, sys.stdin.readline().split())
    x_list = list(map(int, sys.stdin.readline().split()))
    
    # Build adjacency list
    adj = [[] for _ in range(n+1)]  # 1-based
    for _ in range(m):
        u, v = map(int, sys.stdin.readline().split())
        adj[u].append(v)
        adj[v].append(u)
    
    friend_reachables = []
    for x in x_list:
        reachable = {}
        visited = set()
        initial_mask = 1 << (x - 1)
        current_level = [(x, initial_mask)]
        visited.add((x, initial_mask))
        reachable[0] = {x}
        t = 0
        
        while current_level:
            next_level = []
            for u, mask in current_level:
                for v in adj[u]:
                    if not (mask & (1 << (v - 1))):
                        new_mask = mask | (1 << (v - 1))
                        if (v, new_mask) not in visited:
                            visited.add((v, new_mask))
                            next_level.append((v, new_mask))
            if next_level:
                t += 1
                reachable_nodes = set(v for v, _ in next_level)
                reachable[t] = reachable_nodes
                current_level = next_level
            else:
                break
        friend_reachables.append(reachable)
    
    for t in range(n):
        valid = True
        reachables_at_t = []
        for fr in friend_reachables:
            if t not in fr or not fr[t]:
                valid = False
                break
            reachables_at_t.append(fr[t])
        if not valid:
            continue
        
        common = reachables_at_t[0].copy()
        for s in reachables_at_t[1:]:
            common.intersection_update(s)
            if not common:
                break
        if common:
            print("Yes")
            return
    print("No")

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