Submission #71500977

Source Code Expand

from collections import deque

N, M = map(int, input().split())
is_reach = [False] * N
revGraph = [[] for i in range(N)]

for i in range(M):
    u, v = map(int, input().split())
    u -= 1
    v -= 1

    revGraph[v].append(u)

Q = int(input())
for _ in range(Q):
    query = list(map(int, input().split()))

    if query[0] == 1:
        v = query[1]
        v -= 1
        deq = deque([v])
        while deq:
            x = deq.popleft()

            if is_reach[x]:
                continue

            is_reach[x] = True
            for px in revGraph[x]:
                deq.append(px)
    else:
        v = query[1]
        v -= 1
        print("Yes" if is_reach[v] else "No")

Submission Info

Submission Time
Task D - Reachability Query 2
User kokonotsu
Language Python (PyPy 3.11-v7.3.20)
Score 425
Code Size 717 Byte
Status AC
Exec Time 1267 ms
Memory 146268 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 425 / 425
Status
AC × 1
AC × 30
Set Name Test Cases
Sample sample_01.txt
All min.txt, 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, random_21.txt, random_22.txt, random_23.txt, random_24.txt, random_25.txt, random_26.txt, random_27.txt, random_28.txt, sample_01.txt
Case Name Status Exec Time Memory
min.txt AC 70 ms 93828 KiB
random_01.txt AC 1244 ms 138224 KiB
random_02.txt AC 1255 ms 138476 KiB
random_03.txt AC 1007 ms 118992 KiB
random_04.txt AC 1168 ms 121388 KiB
random_05.txt AC 768 ms 111308 KiB
random_06.txt AC 745 ms 110916 KiB
random_07.txt AC 886 ms 114128 KiB
random_08.txt AC 1267 ms 133912 KiB
random_09.txt AC 742 ms 116684 KiB
random_10.txt AC 785 ms 115816 KiB
random_11.txt AC 983 ms 119872 KiB
random_12.txt AC 1199 ms 136360 KiB
random_13.txt AC 623 ms 116076 KiB
random_14.txt AC 568 ms 112852 KiB
random_15.txt AC 812 ms 123212 KiB
random_16.txt AC 921 ms 123640 KiB
random_17.txt AC 1073 ms 139772 KiB
random_18.txt AC 1159 ms 145508 KiB
random_19.txt AC 745 ms 110848 KiB
random_20.txt AC 850 ms 113264 KiB
random_21.txt AC 1238 ms 135368 KiB
random_22.txt AC 1200 ms 145976 KiB
random_23.txt AC 1088 ms 139352 KiB
random_24.txt AC 1162 ms 145572 KiB
random_25.txt AC 1260 ms 146012 KiB
random_26.txt AC 1231 ms 146000 KiB
random_27.txt AC 1089 ms 146268 KiB
random_28.txt AC 896 ms 139304 KiB
sample_01.txt AC 70 ms 93956 KiB