059 - Many Graph Queries（★7） https://atcoder.jp/contests/typical90/tasks/typical90_bg

typical90_bg1.py

# MLEになるバージョン
import sys

sys.setrecursionlimit(10**7)
input = sys.stdin.readline


def dfs(n):
    if (dp[n] >> n) & 1:
        return dp[n]
    dp[n] |= 1 << n
    for nxt in G[n]:
        dp[n] |= dfs(nxt)
    return dp[n]


N, M, Q = map(int, input().split())
G = [[] * N for _ in range(N)]
for _ in range(M):
    x, y = map(lambda n: int(n) - 1, input().split())
    G[x].append(y)

dp = [0] * N
for i in range(N):
    dfs(i)
    G[i] = []
for _ in range(Q):
    a, b = map(lambda n: int(n) - 1, input().split())
    if (dp[a] >> b) & 1:
        print("Yes")
    else:
        print("No")

typical90_bg2.py

# TLEになるバージョン(MLEを避けるため、G(graph)のデータ構造を変更　-> しかし今度は実行時間がかかる 13行目からのwhile文がボトルネックだと思う)
import sys

sys.setrecursionlimit(10**7)
input = sys.stdin.readline

def dfs(n):
    if (dp[n] >> n) & 1:
        return dp[n]
    dp[n] |= 1 << n    
    tmp = G[n]
    nxt = 0
    while tmp > 0:
        if tmp & 1:
            dp[n] |= dfs(nxt)
        tmp >>= 1
        nxt += 1
    return dp[n]


N, M, Q = map(int, input().split())
G = [0 for _ in range(N)]
for _ in range(M):
    x, y = map(lambda n: int(n) - 1, input().split())
    G[y] |= 1 << x

dp = [0] * N
for i in range(N):
    dfs(i)

for _ in range(Q):
    a, b = map(lambda n: int(n) - 1, input().split())
    if (dp[b] >> a) & 1:
        print("Yes")
    else:
        print("No")

typical90_bg3.py

# 想定ソースコード(C++)をPythonへ。しかし、TLEx1という結果に。
import sys

input = sys.stdin.readline
N, M, Q = map(int, input().split())
X, Y = [], []
for _ in range(M):
    x, y = map(lambda n: int(n) - 1, input().split())
    X.append(x)
    Y.append(y)
g = []
for i in range(M):
    g.append(Y[i] * N + X[i])
g.sort()
for i in range(M):
    Y[i], X[i] = divmod(g[i], N)
A, B = [], []
for _ in range(Q):
    a, b = map(lambda n: int(n) - 1, input().split())
    A.append(a)
    B.append(b)
i = 0
while i * 64 < Q:
    dp = [0] * N
    j = i * 64
    while j < (i + 1) * 64 and j < Q:
        dp[A[j]] |= 1 << (j - i * 64)
        j += 1
    for j in range(M):
        dp[Y[j]] |= dp[X[j]]
    j = i * 64
    while j < (i + 1) * 64 and j < Q:
        if (dp[B[j]] >> (j - i * 64)) & 1:
            print("Yes")
        else:
            print("No")
        j += 1
    i += 1