結果

問題 No.1745 Selfish Spies 2 (à la Princess' Perfectionism)
ユーザー qwewe
提出日時 2025-04-24 12:22:16
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,915 bytes
コンパイル時間 290 ms
コンパイル使用メモリ 82,012 KB
実行使用メモリ 168,724 KB
最終ジャッジ日時 2025-04-24 12:24:19
合計ジャッジ時間 19,154 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 27 WA * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

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)]  # Spies are 1-based
    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))

    # Hopcroft-Karp algorithm
    pair_u = [0] * (N + 1)
    pair_v = [0] * (M + 1)
    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 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, N+1):
            if pair_u[u] == 0:
                if dfs(u):
                    result += 1

    # Build residual graph
    residual_graph = [[] for _ in range(N + M + 2)]  # Nodes: 1..N (spies), N+1..N+M (tasks)
    for u in range(1, N+1):
        for v in adj[u]:
            if pair_u[u] == v:
                residual_graph[N + v].append(u)
            else:
                residual_graph[u].append(N + v)

    # Kosaraju's algorithm to find SCC
    def kosaraju(graph, num_nodes):
        visited = [False] * (num_nodes + 1)
        order = []
        
        def dfs(u):
            stack = [(u, False)]
            while stack:
                node, processed = stack.pop()
                if processed:
                    order.append(node)
                    continue
                if visited[node]:
                    continue
                visited[node] = True
                stack.append((node, True))
                for v in graph[node]:
                    if not visited[v]:
                        stack.append((v, False))
        
        for u in range(1, num_nodes + 1):
            if not visited[u]:
                dfs(u)
        
        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)
        
        visited = [False] * (num_nodes + 1)
        component = [0] * (num_nodes + 1)
        current_component = 0
        
        while order:
            u = order.pop()
            if not visited[u]:
                current_component += 1
                stack = [u]
                visited[u] = True
                component[u] = current_component
                while stack:
                    node = stack.pop()
                    for v in reversed_graph[node]:
                        if not visited[v]:
                            visited[v] = True
                            component[v] = current_component
                            stack.append(v)
        return component

    component = kosaraju(residual_graph, N + M)

    # Process each edge
    for S, T in edges:
        if pair_u[S] == T:
            print("Yes")
        else:
            task_node = N + T
            if component[S] == component[task_node]:
                print("Yes")
            else:
                print("No")

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