Submission #17348313


Source Code Expand

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

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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
    add = last_M - M
    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')

nums = np.array(read().split(), np.int64)

main(nums)

Submission Info

Submission Time
Task E - Keep Graph Disconnected
User maspy
Language Python (3.8.2)
Score 700
Code Size 1869 Byte
Status
Exec Time 549 ms
Memory 126664 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 700 / 700
Status
× 1
× 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