結果
| 問題 | 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 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 224 ms
98,184 KB |
| testcase_01 | AC | 219 ms
97,960 KB |
| testcase_02 | AC | 224 ms
98,172 KB |
| testcase_03 | AC | 225 ms
98,040 KB |
| testcase_04 | AC | 807 ms
104,224 KB |
| testcase_05 | AC | 844 ms
104,264 KB |
| testcase_06 | AC | 851 ms
104,304 KB |
| testcase_07 | AC | 630 ms
103,836 KB |
| testcase_08 | AC | 832 ms
104,424 KB |
| testcase_09 | AC | 321 ms
100,120 KB |
| testcase_10 | AC | 302 ms
100,348 KB |
| testcase_11 | AC | 300 ms
99,704 KB |
| testcase_12 | AC | 304 ms
100,520 KB |
| testcase_13 | AC | 314 ms
100,376 KB |
| testcase_14 | AC | 308 ms
99,832 KB |
| testcase_15 | AC | 348 ms
101,408 KB |
| testcase_16 | AC | 351 ms
101,368 KB |
| testcase_17 | AC | 366 ms
101,904 KB |
| testcase_18 | AC | 373 ms
101,644 KB |
| testcase_19 | AC | 312 ms
99,832 KB |
| testcase_20 | AC | 316 ms
100,464 KB |
| testcase_21 | AC | 320 ms
100,908 KB |
| testcase_22 | AC | 298 ms
99,820 KB |
| testcase_23 | AC | 327 ms
100,448 KB |
| testcase_24 | AC | 319 ms
100,124 KB |
| testcase_25 | AC | 306 ms
99,612 KB |
| testcase_26 | AC | 311 ms
100,504 KB |
| testcase_27 | AC | 317 ms
100,132 KB |
| testcase_28 | AC | 316 ms
100,380 KB |
| testcase_29 | AC | 372 ms
101,660 KB |
| testcase_30 | AC | 391 ms
101,288 KB |
| testcase_31 | AC | 452 ms
102,436 KB |
| testcase_32 | AC | 443 ms
102,424 KB |
| testcase_33 | AC | 446 ms
102,432 KB |
| testcase_34 | AC | 450 ms
103,112 KB |
| testcase_35 | AC | 434 ms
102,952 KB |
| testcase_36 | AC | 442 ms
102,936 KB |
| testcase_37 | AC | 402 ms
103,552 KB |
| testcase_38 | AC | 378 ms
103,200 KB |
| testcase_39 | AC | 363 ms
101,280 KB |
| testcase_40 | AC | 425 ms
101,276 KB |
| testcase_41 | AC | 426 ms
101,652 KB |
| testcase_42 | AC | 410 ms
101,544 KB |
| testcase_43 | AC | 396 ms
101,532 KB |
| testcase_44 | AC | 362 ms
101,020 KB |
| testcase_45 | AC | 439 ms
102,564 KB |
| testcase_46 | AC | 357 ms
101,024 KB |
| testcase_47 | AC | 312 ms
100,248 KB |
| testcase_48 | AC | 338 ms
100,764 KB |
| testcase_49 | AC | 346 ms
101,620 KB |
| testcase_50 | AC | 370 ms
101,840 KB |
| testcase_51 | AC | 424 ms
102,160 KB |
| testcase_52 | AC | 438 ms
102,696 KB |
| testcase_53 | AC | 442 ms
102,428 KB |
| testcase_54 | AC | 434 ms
102,684 KB |
| testcase_55 | AC | 445 ms
103,056 KB |
| testcase_56 | AC | 448 ms
102,680 KB |
| testcase_57 | AC | 409 ms
103,928 KB |
| testcase_58 | AC | 391 ms
103,160 KB |
| testcase_59 | AC | 370 ms
100,896 KB |
| testcase_60 | AC | 417 ms
101,544 KB |
| testcase_61 | AC | 429 ms
101,672 KB |
| testcase_62 | AC | 379 ms
101,360 KB |
| testcase_63 | AC | 387 ms
102,000 KB |
| testcase_64 | AC | 373 ms
101,152 KB |
| testcase_65 | AC | 338 ms
100,860 KB |
| testcase_66 | AC | 331 ms
100,884 KB |
| testcase_67 | AC | 332 ms
100,260 KB |
| testcase_68 | AC | 307 ms
99,468 KB |
| testcase_69 | AC | 336 ms
100,252 KB |
| testcase_70 | AC | 385 ms
102,288 KB |
| testcase_71 | AC | 400 ms
102,556 KB |
| testcase_72 | AC | 393 ms
103,200 KB |
| testcase_73 | AC | 384 ms
103,452 KB |
| testcase_74 | AC | 388 ms
103,072 KB |
| testcase_75 | AC | 403 ms
103,072 KB |
| testcase_76 | AC | 392 ms
103,452 KB |
| testcase_77 | AC | 401 ms
102,812 KB |
| testcase_78 | AC | 400 ms
103,072 KB |
| testcase_79 | AC | 320 ms
100,764 KB |
| testcase_80 | AC | 348 ms
100,976 KB |
| testcase_81 | AC | 346 ms
100,984 KB |
| testcase_82 | AC | 350 ms
101,312 KB |
| testcase_83 | AC | 345 ms
100,776 KB |
| testcase_84 | AC | 333 ms
100,768 KB |
| testcase_85 | AC | 351 ms
101,264 KB |
| testcase_86 | AC | 332 ms
100,516 KB |
| testcase_87 | AC | 341 ms
101,116 KB |
| testcase_88 | AC | 382 ms
102,564 KB |
| testcase_89 | AC | 361 ms
101,500 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)