提出 #71511324

---

ソースコード 拡げる

import sys
sys.setrecursionlimit(10 ** 6)

import numpy as np
from numba import jit, boolean, int64, float64, typeof, types, typeof, objmode
# jit = lambda func, *args, **kwargs: func



def main():
    from io import StringIO
    execute(StringIO(sample), sys.stderr)
    print("-- ^sample! --", file=sys.stderr)

    execute(sys.stdin, sys.stdout)

    if len(solve.nopython_signatures) != 1:
        raise KeyboardInterrupt("!! Unexpected: wrong use of jit !!")

def execute(src, dst):

    N, M, = map(int, src.readline().split())
    XY1d = np.fromstring("\n".join(src.readline().strip() for _ in range(M)), dtype=np.int64, sep=' ')
    Q, = map(int, src.readline().split())
    Q1d = np.fromstring("\n".join(src.readline().strip() for _ in range(Q)), dtype=np.int64, sep=' ')
    ans = solve(N, M, XY1d, Q, Q1d )
    print(*ans, sep="\n", file=dst)

sample = """\
5 6
1 2
2 3
3 1
4 5
1 4
2 5
5
1 3
2 1
2 4
1 5
2 4
"""

@jit(nopython=True, cache=True)
def solve(N, M, XY1d, Q, Q1d ):
    empty = [i for i in range(0)]
    toE1 = [empty.copy() for _n in range(N + 1) ]
    fromE1 = [empty.copy() for _n in range(N + 1) ]
    for x, y in XY1d.reshape((M,2,)):
        toE1[x].append(y)
        fromE1[y].append(x)

    ans = []
    isblack = np.zeros((N+1,) , dtype=np.bool_)
    for qty , qv in Q1d.reshape((Q,2,)):
        if qty == 1:
            whileDFS(qv , fromE1 , isblack)
        if qty == 2:
            if isblack[qv] :
                ans.append("Yes")
            else:
                ans.append("No")
    1
    return ans

@jit(nopython=True, cache=True)
def whileDFS(id_start, E, isblack):
    # visited = np.zeros(shape=len(E_ll), dtype=np.bool_)
    visited = isblack
    # 開始処理
    stack = []
    stack.append(id_start)
    while stack:
        id_now = stack.pop()
        if visited[id_now] == True:
            continue    # 調査済みチェックは本当に必要か？？？？
        visited[id_now] = True
        # 行きがけでの処理
        # -
        for id_next in E[id_now]:
            if visited[id_next] == False:
            # if id_next not in visited:
                stack.append(id_next)
        # 末端での処理
        # -
        continue
    return None



main()

提出情報

ジャッジ結果