結果

問題 No.1775 Love Triangle 2
コンテスト
ユーザー hitonanode
提出日時 2021-11-26 02:07:23
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 851 ms / 8,000 ms
コード長 3,443 bytes
コンパイル時間 416 ms
コンパイル使用メモリ 82,244 KB
実行使用メモリ 104,424 KB
最終ジャッジ日時 2024-07-03 21:15:06
合計ジャッジ時間 37,552 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 90
権限があれば一括ダウンロードができます

ソースコード

diff # 

from functools import lru_cache
import itertools
import random

random.seed(530629)


@lru_cache(maxsize=None)
def rec(x: int, y: int) -> int:
    if x == 0 or y == 0:
        return 0
    if x < y:
        x ^= y
        y ^= x
        x ^= y
    if y == 1:
        return x
    shift = 16 // 2
    while True:
        mask = (1 << shift) - 1
        if y >> shift:
            v00 = rec(x & mask, y & mask)
            v01 = rec(x & mask, y >> shift)
            v10 = rec(x >> shift, y & mask)
            v11 = rec(x >> shift, y >> shift)
            return v00 ^ ((v01 ^ v10 ^ v11) << shift) ^ rec(v11, 1 << (shift - 1))
        elif x >> shift:
            return (rec(x >> shift, y) << shift) ^ rec(x & mask, y)
        shift //= 2


small_table = [[rec(i, j) for j in range(256)] for i in range(256)]
precalc00 = [rec(rec(1 << (8 * 0), 1 << (8 * 0)), i) for i in range(256)]
precalc01 = [rec(rec(1 << (8 * 0), 1 << (8 * 1)), i) for i in range(256)]
precalc11 = [rec(rec(1 << (8 * 1), 1 << (8 * 1)), i) for i in range(256)]


def nim_p(x: int, y: int) -> int:
    ret = precalc00[small_table[x & 255][y & 255]] \
        ^ precalc01[small_table[(x >> 8) & 255][y & 255]] \
        ^ precalc01[small_table[x & 255][(y >> 8) & 255]] \
        ^ precalc11[small_table[(x >> 8) & 255][(y >> 8) & 255]]
    return ret


n, m = map(int, input().split())
x, y, z = map(int, input().split())
x -= 1
y -= 1
z -= 1

edge_exists = [[1] * n for _ in range(n)]

for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    edge_exists[a][b] = edge_exists[b][a] = 0

ret = n + 1

to = [list() for _ in range(n + 1)]

for _ in range(2):
    for i, j in itertools.combinations(range(n), 2):
        if not edge_exists[i][j]:
            continue
        w = random.randint(0, 65535)
        wn = random.randint(0, 65535)
        for t in range(2):
            if j != x:
                to[i].append((j, w))
            else:
                to[i].append((n, wn))
            i, j = j, i

    # dp = [[[[0 for _ in range(n + 1)] for _ in range(n + 1)] for _ in range(2)] for _ in range(2)]
    dp = [[[0 for _ in range(n + 1)] for _ in range(n + 1)] for _ in range(4)]
    # dp[0][0][x][n] = 1
    dp[0][x][n] = 1

    for d in range(n):
        found = False
        # dpnxt = [[[[0 for _ in range(n + 1)] for _ in range(n + 1)] for _ in range(2)] for _ in range(2)]
        dpnxt = [[[0 for _ in range(n + 1)] for _ in range(n + 1)] for _ in range(4)]
        for visy, visz in itertools.product(range(2), repeat=2):
            for now in range(n):
                s = 0
                # v = dp[visy][visz][now]
                v = dp[visy * 2 + visz][now]
                for i in v:
                    s ^= i
                for nxt, w in to[now]:
                    if (nxt == y and visy) or (nxt == z and visz):
                        continue
                    # dpnxt[visy | (y == nxt)][visz | (z == nxt)][nxt][now] ^= nim_p(s ^ v[nxt], w)
                    dpnxt[(visy | (y == nxt)) * 2 + (visz | (z == nxt))][nxt][now] ^= nim_p(s ^ v[nxt], w)

        dp = dpnxt
        for i in range(n):
            # if dp[1][1][n][i]:
            if dp[3][n][i]:
                found = True

        if found:
            ret = min(ret, d + 1)
            break

if ret <= n:
    print(ret)
else:
    print(-1)
0