Contest Duration: ~ (local time) (100 minutes) Back to Home

Submission #17348313

Source Code Expand

Copy
```import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

uf_t = numba.types.UniTuple(i8[:], 2)

@njit((uf_t, i8), cache=True)
def find_root(uf, x):
root = uf[0]
while root[x] != x:
root[x] = root[root[x]]
x = root[x]
return x

@njit((uf_t, i8, i8), cache=True)
def merge(uf, x, y):
root, size = uf
x, y = find_root(uf, x), find_root(uf, y)
if x == y:
return False
if size[x] < size[y]:
x, y = y, x
size[x] += size[y]
root[y] = root[x]
return True

@njit((i8, i8, i8[:]), cache=True)
def solve(N, M, AB):
last_M = N * (N - 1) // 2
if N % 2 == 1:
# 運命は決まっている
return add % 2 == 1
# 以下、偶数頂点
A, B = AB[::2], AB[1::2]
root = np.arange(N + 1, dtype=np.int64)
size = np.ones_like(root)
uf = (root, size)
for i in range(len(A)):
merge(uf, A[i], B[i])
r0, r1 = find_root(uf, 1), find_root(uf, N)
s0, s1 = size[r0], size[r1]
# 先手の理想形は？
if add % 2 == 0:
# 先手は (od, od) を目指すことになる
if s0 % 2 == 0 and s1 % 2 == 0:
return False
return True
else:
# 先手は (ev, ev) を目指すことになる
if s0 % 2 == 1 and s1 % 2 == 1:
return False
return True

@njit((i8[:], ), cache=True)
def main(nums):
T, nums = nums[0], nums[1:]
for _ in range(T):
N, M = nums[:2]
nums = nums[2:]
AB = nums[:M + M]
nums = nums[M + M:]
print('First' if solve(N, M, AB) else 'Second')

main(nums)```

#### Submission Info

Submission Time 2020-10-11 23:30:15+0900 E - Keep Graph Disconnected maspy Python (3.8.2) 700 1869 Byte AC 549 ms 126664 KB

#### Judge Result

Set Name Sample All
Score / Max Score 0 / 0 700 / 700
Status
 AC × 1
 AC × 21
Set Name Test Cases
Sample sample_01.txt
All random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, random_19.txt, random_20.txt, sample_01.txt
Case Name Status Exec Time Memory
random_01.txt 523 ms 106500 KB
random_02.txt 515 ms 113480 KB
random_03.txt 530 ms 119936 KB
random_04.txt 534 ms 120264 KB
random_05.txt 538 ms 123292 KB
random_06.txt 538 ms 122640 KB
random_07.txt 528 ms 119948 KB
random_08.txt 541 ms 124608 KB
random_09.txt 549 ms 126284 KB
random_10.txt 548 ms 126664 KB
random_11.txt 531 ms 119148 KB
random_12.txt 533 ms 119116 KB
random_13.txt 536 ms 119080 KB
random_14.txt 534 ms 119056 KB
random_15.txt 535 ms 118672 KB
random_16.txt 531 ms 119108 KB
random_17.txt 528 ms 119656 KB
random_18.txt 532 ms 118668 KB
random_19.txt 482 ms 107416 KB
random_20.txt 526 ms 118828 KB
sample_01.txt 481 ms 106144 KB