#719652 (PyPy3) No.1775 Love Triangle 2

• 問題: No.1775 Love Triangle 2
• ユーザー: 👑 hitonanode
• 提出日時: 2021-11-26 02:07:23
• 言語: PyPy3 (7.3.15)
• 結果: AC
• 実行時間: 909 ms / 8,000 ms
• コード長: 3,443 bytes
• コンパイル時間: 350 ms
• コンパイル使用メモリ: 87,224 KB
• 実行使用メモリ: 107,544 KB
• 最終ジャッジ日時: 2023-09-16 22:20:08
• 合計ジャッジ時間: 42,833 ms
• ジャッジサーバーID （参考情報）: judge15 / judge11

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	270 ms; 99,812 KB
testcase_01	AC	274 ms; 99,668 KB
testcase_02	AC	278 ms; 99,804 KB
testcase_03	AC	282 ms; 99,880 KB
testcase_04	AC	875 ms; 106,356 KB
testcase_05	AC	909 ms; 106,856 KB
testcase_06	AC	888 ms; 106,540 KB
testcase_07	AC	645 ms; 106,432 KB
testcase_08	AC	891 ms; 107,544 KB
testcase_09	AC	349 ms; 102,820 KB
testcase_10	AC	350 ms; 102,972 KB
testcase_11	AC	355 ms; 102,704 KB
testcase_12	AC	354 ms; 102,788 KB
testcase_13	AC	360 ms; 102,664 KB
testcase_14	AC	366 ms; 102,648 KB
testcase_15	AC	408 ms; 103,952 KB
testcase_16	AC	410 ms; 104,252 KB
testcase_17	AC	426 ms; 104,440 KB
testcase_18	AC	434 ms; 104,584 KB
testcase_19	AC	360 ms; 102,312 KB
testcase_20	AC	374 ms; 103,288 KB
testcase_21	AC	366 ms; 102,744 KB
testcase_22	AC	361 ms; 102,316 KB
testcase_23	AC	370 ms; 103,140 KB
testcase_24	AC	359 ms; 102,656 KB
testcase_25	AC	360 ms; 103,228 KB
testcase_26	AC	361 ms; 102,844 KB
testcase_27	AC	350 ms; 102,712 KB
testcase_28	AC	357 ms; 102,856 KB
testcase_29	AC	400 ms; 105,288 KB
testcase_30	AC	417 ms; 104,020 KB
testcase_31	AC	492 ms; 104,948 KB
testcase_32	AC	510 ms; 104,816 KB
testcase_33	AC	514 ms; 105,512 KB
testcase_34	AC	507 ms; 104,940 KB
testcase_35	AC	494 ms; 106,524 KB
testcase_36	AC	491 ms; 105,648 KB
testcase_37	AC	461 ms; 105,680 KB
testcase_38	AC	448 ms; 105,888 KB
testcase_39	AC	438 ms; 104,124 KB
testcase_40	AC	484 ms; 104,904 KB
testcase_41	AC	478 ms; 104,332 KB
testcase_42	AC	467 ms; 104,500 KB
testcase_43	AC	446 ms; 104,092 KB
testcase_44	AC	415 ms; 104,020 KB
testcase_45	AC	482 ms; 104,924 KB
testcase_46	AC	420 ms; 103,796 KB
testcase_47	AC	374 ms; 102,924 KB
testcase_48	AC	391 ms; 103,336 KB
testcase_49	AC	412 ms; 103,908 KB
testcase_50	AC	436 ms; 104,036 KB
testcase_51	AC	492 ms; 105,116 KB
testcase_52	AC	497 ms; 105,792 KB
testcase_53	AC	515 ms; 104,984 KB
testcase_54	AC	494 ms; 105,128 KB
testcase_55	AC	483 ms; 106,180 KB
testcase_56	AC	460 ms; 105,880 KB
testcase_57	AC	442 ms; 105,848 KB
testcase_58	AC	426 ms; 105,660 KB
testcase_59	AC	415 ms; 104,648 KB
testcase_60	AC	447 ms; 106,048 KB
testcase_61	AC	468 ms; 104,180 KB
testcase_62	AC	430 ms; 103,400 KB
testcase_63	AC	430 ms; 103,984 KB
testcase_64	AC	429 ms; 104,168 KB
testcase_65	AC	383 ms; 102,552 KB
testcase_66	AC	374 ms; 103,124 KB
testcase_67	AC	368 ms; 103,632 KB
testcase_68	AC	363 ms; 102,720 KB
testcase_69	AC	388 ms; 103,336 KB
testcase_70	AC	434 ms; 104,416 KB
testcase_71	AC	427 ms; 105,060 KB
testcase_72	AC	418 ms; 105,420 KB
testcase_73	AC	427 ms; 104,744 KB
testcase_74	AC	423 ms; 106,088 KB
testcase_75	AC	430 ms; 106,224 KB
testcase_76	AC	408 ms; 105,120 KB
testcase_77	AC	433 ms; 105,652 KB
testcase_78	AC	431 ms; 106,396 KB
testcase_79	AC	434 ms; 102,908 KB
testcase_80	AC	390 ms; 103,936 KB
testcase_81	AC	404 ms; 103,568 KB
testcase_82	AC	392 ms; 104,296 KB
testcase_83	AC	403 ms; 103,776 KB
testcase_84	AC	385 ms; 103,820 KB
testcase_85	AC	404 ms; 103,588 KB
testcase_86	AC	383 ms; 102,544 KB
testcase_87	AC	399 ms; 103,676 KB
testcase_88	AC	446 ms; 105,256 KB
testcase_89	AC	410 ms; 104,160 KB

ソースコード

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)