結果

問題 No.1744 Selfish Spies 1 (à la Princess' Perfectionism)
コンテスト
ユーザー lam6er
提出日時 2025-04-16 00:10:22
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,734 bytes
コンパイル時間 471 ms
コンパイル使用メモリ 81,888 KB
実行使用メモリ 103,904 KB
最終ジャッジ日時 2025-04-16 00:11:35
合計ジャッジ時間 6,170 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 21 WA * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque, defaultdict

def hopcroft_karp(graph, N, M):
    pair_u = [0] * (N + 1)  # spy 1-based
    pair_v = [0] * (M + 1)  # task 1-based
    dist = [0] * (N + 1)

    def bfs():
        queue = deque()
        for u in range(1, N + 1):
            if pair_u[u] == 0:
                dist[u] = 0
                queue.append(u)
            else:
                dist[u] = float('inf')
        dist[0] = float('inf')
        while queue:
            u = queue.popleft()
            if dist[u] < dist[0]:
                for v in graph[u]:
                    if dist[pair_v[v]] == float('inf'):
                        dist[pair_v[v]] = dist[u] + 1
                        queue.append(pair_v[v])
        return dist[0] != float('inf')

    def dfs(u):
        if u != 0:
            for v in graph[u]:
                if dist[pair_v[v]] == dist[u] + 1:
                    if dfs(pair_v[v]):
                        pair_u[u] = v
                        pair_v[v] = u
                        return True
            dist[u] = float('inf')
            return False
        return True

    result = 0
    while bfs():
        for u in range(1, N + 1):
            if pair_u[u] == 0:
                if dfs(u):
                    result += 1
    return pair_u, pair_v

def main():
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    M = int(input[ptr])
    ptr += 1
    L = int(input[ptr])
    ptr += 1

    edges = []
    adj = defaultdict(list)
    for _ in range(L):
        s = int(input[ptr])
        ptr += 1
        t = int(input[ptr])
        ptr += 1
        edges.append((s, t))
        adj[s].append(t)

    # Compute maximum matching
    pair_u, pair_v = hopcroft_karp(adj, N, M)

    # Build residual graph
    residual = defaultdict(list)
    for s, t in edges:
        if pair_u[s] == t:
            residual[N + t].append(s)
        else:
            residual[s].append(N + t)

    # Collect all nodes (spies and tasks)
    nodes = set()
    for s in range(1, N + 1):
        nodes.add(s)
    for t in range(1, M + 1):
        nodes.add(N + t)
    nodes = list(nodes)

    # Kosaraju's algorithm to find SCCs
    visited = set()
    order = []

    def dfs1(u):
        stack = [(u, False)]
        while stack:
            node, processed = stack.pop()
            if processed:
                order.append(node)
                continue
            if node in visited:
                continue
            visited.add(node)
            stack.append((node, True))
            for v in residual.get(node, []):
                if v not in visited:
                    stack.append((v, False))

    for u in nodes:
        if u not in visited:
            dfs1(u)

    reversed_residual = defaultdict(list)
    for u in residual:
        for v in residual[u]:
            reversed_residual[v].append(u)

    visited = set()
    component = {}
    current = 0

    while order:
        u = order.pop()
        if u in visited:
            continue
        stack = [u]
        visited.add(u)
        component[u] = current
        while stack:
            node = stack.pop()
            for v in reversed_residual.get(node, []):
                if v not in visited:
                    visited.add(v)
                    component[v] = current
                    stack.append(v)
        current += 1

    # Process each query
    for s, t in edges:
        if pair_u[s] != t:
            print("Yes")
        else:
            node_s = s
            node_t = N + t
            if component.get(node_s, -1) == component.get(node_t, -2):
                print("Yes")
            else:
                print("No")

if __name__ == "__main__":
    main()
0