結果

問題 No.2948 move move rotti
ユーザー lam6er
提出日時 2025-03-20 20:20:43
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,166 ms / 4,000 ms
コード長 1,830 bytes
コンパイル時間 392 ms
コンパイル使用メモリ 82,516 KB
実行使用メモリ 213,188 KB
最終ジャッジ日時 2025-03-20 20:22:09
合計ジャッジ時間 17,044 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def main():
    n, m, k = map(int, sys.stdin.readline().split())
    friends = list(map(int, sys.stdin.readline().split()))
    adj = [[] for _ in range(n + 1)]
    for _ in range(m):
        u, v = map(int, sys.stdin.readline().split())
        adj[u].append(v)
        adj[v].append(u)

    all_reachable = []
    for x in friends:
        reachable = [set() for _ in range(n)]
        start = x
        initial_mask = 1 << (start - 1)
        visited = set()
        queue = deque()
        queue.append((start, initial_mask))
        visited.add((start, initial_mask))
        t0 = (initial_mask.bit_count() - 1)
        reachable[t0].add(start)
        while queue:
            u, mask = queue.popleft()
            current_t = mask.bit_count() - 1
            for v in adj[u]:
                if not (mask & (1 << (v - 1))):
                    new_mask = mask | (1 << (v - 1))
                    new_t = new_mask.bit_count() - 1
                    if (v, new_mask) not in visited:
                        visited.add((v, new_mask))
                        reachable[new_t].add(v)
                        queue.append((v, new_mask))
        all_reachable.append(reachable)

    max_t = n - 1
    for t in range(max_t + 1):
        common = None
        possible = True
        for i in range(k):
            if not all_reachable[i][t]:
                possible = False
                break
            if common is None:
                common = all_reachable[i][t].copy()
            else:
                common.intersection_update(all_reachable[i][t])
                if not common:
                    possible = False
                    break
        if possible and common:
            print("Yes")
            return
    print("No")

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