結果

問題 No.1745 Selfish Spies 2 (à la Princess' Perfectionism)
コンテスト
ユーザー qwewe
提出日時 2025-05-14 12:47:20
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,849 bytes
コンパイル時間 547 ms
コンパイル使用メモリ 82,416 KB
実行使用メモリ 160,248 KB
最終ジャッジ日時 2025-05-14 12:48:01
合計ジャッジ時間 20,099 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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

    edges = []
    adj = [[] for _ in range(N)]
    for _ in range(L):
        S = int(input[ptr]) - 1; ptr += 1
        T = int(input[ptr]) - 1; ptr += 1
        edges.append((S, T))
        adj[S].append(T)

    # Hopcroft-Karp algorithm to find maximum matching
    pair_u = [-1] * N
    pair_v = [-1] * M
    dist = [0] * N

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

    def dfs(u):
        for v in adj[u]:
            if pair_v[v] == -1 or (dist[pair_v[v]] == dist[u] + 1 and dfs(pair_v[v])):
                pair_u[u] = v
                pair_v[v] = u
                return True
        dist[u] = float('inf')
        return False

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

    # Build residual graph
    residual = [[] for _ in range(N + M)]
    for s, t in edges:
        if pair_u[s] == t:
            task_node = N + t
            residual[task_node].append(s)
        else:
            task_node = N + t
            residual[s].append(task_node)

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

    component = kosaraju(residual, N + M)

    # Process each query
    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