結果

問題 No.1744 Selfish Spies 1 (à la Princess' Perfectionism)
ユーザー lam6er
提出日時 2025-03-31 17:35:50
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 4,455 bytes
コンパイル時間 187 ms
コンパイル使用メモリ 82,288 KB
実行使用メモリ 105,180 KB
最終ジャッジ日時 2025-03-31 17:36:39
合計ジャッジ時間 5,957 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 21 WA * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def hopcroft_karp(U_size, V_size, adj):
    pair_U = [0] * (U_size + 1)  # Pair for spies (1-based)
    pair_V = [0] * (V_size + 1)  # Pair for tasks (1-based)
    dist = [0] * (U_size + 1)    # Distance for BFS layers

    def bfs():
        queue = deque()
        for u in range(1, U_size + 1):
            if pair_U[u] == 0:
                dist[u] = 0
                queue.append(u)
            else:
                dist[u] = float('inf')
        dist[0] = float('inf')  # Dummy node
        while queue:
            u = queue.popleft()
            if dist[u] < dist[0]:
                for v in adj[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 adj[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, U_size + 1):
            if pair_U[u] == 0:
                if dfs(u):
                    result += 1
    return pair_U, pair_V, result

def kosaraju_scc(graph, num_nodes):
    visited = [False] * (num_nodes + 1)
    order = []

    # First pass to get finishing order
    for node in range(1, num_nodes + 1):
        if not visited[node]:
            stack = [(node, False)]
            while stack:
                v, processed = stack.pop()
                if processed:
                    order.append(v)
                    continue
                if visited[v]:
                    continue
                visited[v] = True
                stack.append((v, True))
                for neighbor in reversed(graph[v]):
                    if not visited[neighbor]:
                        stack.append((neighbor, False))

    # Build reversed graph
    reversed_graph = [[] for _ in range(num_nodes + 1)]
    for u in range(1, num_nodes + 1):
        for v in graph[u]:
            reversed_graph[v].append(u)

    # Second pass to get SCCs
    visited = [False] * (num_nodes + 1)
    scc_ids = [0] * (num_nodes + 1)
    component_id = 0

    while order:
        node = order.pop()
        if not visited[node]:
            stack = [node]
            visited[node] = True
            component = []
            while stack:
                v = stack.pop()
                component.append(v)
                for neighbor in reversed_graph[v]:
                    if not visited[neighbor]:
                        visited[neighbor] = True
                        stack.append(neighbor)
            for v in component:
                scc_ids[v] = component_id
            component_id += 1

    return scc_ids

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

    adj = [[] for _ in range(N+1)]  # adj[u] contains tasks (v) that u can do
    edges = []
    for _ in range(L):
        S = int(input[ptr]); ptr +=1
        T = int(input[ptr]); ptr +=1
        adj[S].append(T)
        edges.append((S, T))

    # Compute maximum matching
    pair_U, pair_V, max_matching = hopcroft_karp(N, M, adj)

    # Build residual graph
    total_nodes = N + M
    residual_graph = [[] for _ in range(total_nodes +1)]  # 1-based

    for S, T in edges:
        # For each edge (S, T)
        # Check if it's matched
        if pair_U[S] == T:
            # Matched edge: task T → spy S in residual
            residual_graph[N + T].append(S)
        else:
            # Unmatched edge: spy S → task T in residual
            residual_graph[S].append(N + T)

    # Compute SCCs
    scc_ids = kosaraju_scc(residual_graph, total_nodes)

    # Process each edge
    for S, T in edges:
        if pair_U[S] == T:
            # Check if S (spy node) and T's node (N + T) are in the same SCC
            spy_node = S
            task_node = N + T
            if scc_ids[spy_node] == scc_ids[task_node]:
                print("Yes")
            else:
                print("No")
        else:
            # Unused edge, answer is Yes
            print("Yes")

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