Day 180-Q1 — 2026-10-16 | 速さ 3 の泥棒と「警官を通り抜けられるか」（速さ s と通り抜けの有無で行き先の集合を作り直して後退解析。4 頂点の道で結果が分かれる）

📋 コピーimport sys


def solve(n, edges, s, passing):
    adj = [0] * n
    nbr = [[] for _ in range(n)]
    for u, v in edges:
        adj[u] |= 1 << v; adj[v] |= 1 << u
        nbr[u].append(v); nbr[v].append(u)
    full = (1 << n) - 1
    # mv[c][r]：警官が c にいるとき、泥棒が r から 1 手で行ける頂点（留まるを含む）
    mv = []
    if passing:
        ball = [1 << v for v in range(n)]
        for _ in range(s):
            ball = grow(ball, nbr)
        for c in range(n):
            nc = ~(1 << c)
            mv.append([b & nc for b in ball])
    else:
        for c in range(n):
            ball = [1 << v for v in range(n)]
            ball[c] = 0
            for _ in range(s):
                ball = grow(ball, nbr)
                ball[c] = 0
            mv.append(ball)
    done = [0] * n                      # done[c]：T(c, r) が確定した r の集合
    knownR = [1 << c for c in range(n)]  # 泥棒の手番 (c, r) で値が確定した r（r=c は無い局面）
    new = [adj[c] for c in range(n)]    # T = 1：隣の泥棒をそのまま捕まえる
    t = 1
    maxT = [0] * n
    while any(new):
        for c in range(n):
            if new[c]:
                done[c] |= new[c]
                if done[c] | (1 << c) == full:
                    maxT[c] = t
        # 泥棒の手番 (c', r)：行き先がすべて確定したら値 t
        newR = [0] * n
        for c in range(n):
            if not new[c]:
                continue
            d = done[c]
            unk = full & ~knownR[c]
            row = mv[c]
            x = unk
            got = 0
            while x:
                low = x & -x
                r = low.bit_length() - 1
                if row[r] & ~d == 0:
                    got |= low
                x ^= low
            knownR[c] |= got
            newR[c] = got
        # 警官の手番 (c, r)：c の隣か c 自身の c' で泥棒の値が t なら T = t + 1
        nxt = [0] * n
        for cp in range(n):
            g = newR[cp]
            if g:
                nxt[cp] |= g
                for c in nbr[cp]:
                    nxt[c] |= g
        new = [nxt[c] & ~done[c] & ~(1 << c) for c in range(n)]
        t += 1
    if n == 1:
        return 0
    best = -1
    for c in range(n):
        if done[c] | (1 << c) == full and (best < 0 or maxT[c] < best):
            best = maxT[c]
    return best


def grow(ball, nbr):
    """半径を 1 増やす：自分の球と隣の球の和"""
    out = ball[:]
    for v, b in enumerate(ball):
        if b:
            for u in nbr[v]:
                out[u] |= b
    return out


def main():
    data = sys.stdin.buffer.read().split()
    n, m, s, p = int(data[0]), int(data[1]), int(data[2]), int(data[3])
    edges = [(int(data[4 + 2 * i]) - 1, int(data[5 + 2 * i]) - 1) for i in range(m)]
    print(solve(n, edges, s, p))


if __name__ == "__main__":
    main()