Submission #21273753

---

Source Code Expand

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

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

def from_read(dtype=np.int64):
    return np.fromstring(read().decode(), dtype=dtype, sep=' ')


def from_readline(dtype=np.int64):
    return np.fromstring(readline().decode(), dtype=dtype, sep=' ')

@njit
def max_flow(N, G, source, sink):
    """G は、(from, to, cap) の入った (M,3) array。
    逆辺は持たせなくてよい"""
    M = len(G)
    H = G
    G = np.empty((M + M, 4), np.int64)
    for i in range(M):
        fr, to, cap = H[i]
        G[2 * i] = (fr, to, cap, 0)
        G[2 * i + 1] = (to, fr, 0, 0)
    argsort = np.argsort(G[:, 0])
    rank = np.argsort(argsort)
    G = G[argsort]
    for i in range(M):
        r1 = rank[2 * i]
        r2 = rank[2 * i + 1]
        G[r1, 3] = r2
        G[r2, 3] = r1
    idx = np.searchsorted(G[:, 0], np.arange(N + 1))
    level = np.zeros(N, np.int32)
    prog = np.zeros(N, np.int32)
    deq = np.empty(N, np.int32)
    stack = np.empty((N, 2), np.int64)

    def bfs():
        nonlocal N, G, source, sink, idx, level, prog, deq
        level[:] = 0
        level[source] = 1
        l, r = 0, 0
        deq[r], r = source, r + 1
        while l < r:
            v, l = deq[l], l + 1
            for e in range(idx[v], idx[v + 1]):
                fr, to, cap, rev = G[e]
                if not cap:
                    continue
                if level[to]:
                    continue
                level[to] = level[v] + 1
                if to == sink:
                    return
                deq[r], r = to, r + 1
        return

    def dfs():
        nonlocal N, G, source, sink, idx, level, prog, stack
        INF = 1 << 60
        ascend = False
        ff = 0
        s = 0
        stack[s], s = (source, INF), s + 1
        while s:
            if ff:
                v, f = stack[s - 1]
                s -= 1
                p = prog[v]
                _, to, cap, rev = G[p]
                G[p][2] -= ff
                G[rev][2] += ff
                continue
            v, f = stack[s - 1]
            if v == sink:
                ff = f
                s -= 1
                continue
            if ascend:
                prog[v] += 1
            find = False
            p = prog[v]
            for e in range(p, idx[v + 1]):
                _, to, cap, rev = G[e]
                prog[v] = e
                if not cap:
                    continue
                if level[to] <= level[v]:
                    continue
                find = True
                break
            if not find:
                ascend = True
                s -= 1
                continue
            ascend = False
            x = min(f, cap)
            stack[s], s = (to, x), s + 1
        return ff

    flow = 0
    while True:
        bfs()
        if not level[sink]:
            break
        prog[:] = idx[:N]
        while True:
            f = dfs()
            if not f:
                break
            flow += f
    return flow, G

@njit
def scc_dfs(N, G, idx, low, ord, ids, visited, now_ord, group_num, vis_i, v):
    low[v] = ord[v] = now_ord
    now_ord += 1
    visited[vis_i], vis_i = v, vis_i + 1
    for e in range(idx[v], idx[v + 1]):
        to = G[e, 1]
        if ord[to] == -1:
            now_ord, group_num, vis_i = \
                scc_dfs(N, G, idx, low, ord, ids,
                        visited, now_ord, group_num,
                        vis_i, to)
            low[v] = min(low[v], low[to])
        else:
            low[v] = min(low[v], ord[to])
    if low[v] == ord[v]:
        while True:
            u, vis_i = visited[vis_i - 1], vis_i - 1
            ord[u] = N
            ids[u] = group_num
            if u == v:
                break
        group_num += 1
    return now_ord, group_num, vis_i


@njit
def scc(N, G):
    idx = np.searchsorted(G[:, 0], np.arange(N + 1))
    low = np.zeros(N, np.int64)
    ord = np.zeros(N, np.int64) - 1
    now_ord = 0
    group_num = 0
    visited, vis_i = np.empty(N, np.int64), 0
    ids = np.zeros(N, np.int64)
    for v in range(N):
        if ord[v] == -1:
            now_ord, group_num, vis_i = \
                scc_dfs(N, G, idx, low, ord, ids,
                        visited, now_ord, group_num,
                        vis_i, v)
    comp = group_num - ids - 1
    n_comp = group_num
    return n_comp, comp

@njit
def bfs_01(N, G, v):
    INF = 1 << 60
    idx = np.searchsorted(G[:, 0], np.arange(N + 2))
    dist = np.full(N + 1, INF, np.int64)
    dist[v] = 0
    q, l, r = np.empty(N + 10, np.int64), 0, 0
    q[r], r = v, r + 1
    while l < r:
        v, l = q[l], l + 1
        for e in range(idx[v], idx[v + 1]):
            w = G[e, 1]
            if dist[w] > dist[v] + 1:
                q[r], r = w, r + 1
                dist[w] = dist[v] + 1
    return dist

@njit((i8, i8[:, :], i8[:, :]), cache=True)
def main(N, G, CD):
    INF = 1 << 60
    flow, res_G = max_flow(N + 1, G, 1, N)
    H = res_G[res_G[:, 2] > 0][:, :2]
    n_comp, comp = scc(N + 1, H)
    """
    topological 順序で、必ず source よりも後ろに来るパターンと、sink よりも前に来るパターン
    """
    after_s = bfs_01(N, H, 1) < INF
    H = H[:, ::-1]
    H = H[np.argsort(H[:, 0], kind='mergesort')]
    before_t = bfs_01(N, H, N) < INF
    comp[after_s] = comp[1]
    comp[before_t] = comp[N]

    for q in range(len(CD)):
        c, d = CD[q]
        if comp[c] == comp[d]:
            print('YES NO')
        elif comp[c] == comp[1] and comp[d] == comp[N]:
            print('NO YES')
        elif comp[d] == comp[1] and comp[c] == comp[N]:
            print('NO YES')
        else:
            print('YES YES')

N, M = from_readline()
nums = from_read()
G = nums[:M + M].reshape(M, 2)
CD = nums[M + M + 1:].reshape(-1, 2)

G = np.append(G, np.ones(M, np.int64).reshape(M, 1), axis=1)

main(N, G, CD)

Submission Info

Judge Result