結果

問題 No.1745 Selfish Spies 2 (à la Princess' Perfectionism)
ユーザー qwewe
提出日時 2025-05-14 12:49:04
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 4,418 bytes
コンパイル時間 309 ms
コンパイル使用メモリ 82,168 KB
実行使用メモリ 167,004 KB
最終ジャッジ日時 2025-05-14 12:50:51
合計ジャッジ時間 21,129 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 7 WA * 52
権限があれば一括ダウンロードができます

ソースコード

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)]
    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):
        stack = [(u, iter(adj[u]))]
        path = []
        found = False
        while stack:
            node, it = stack[-1]
            try:
                v = next(it)
                if dist[pair_V[v]] == dist[node] + 1:
                    path.append((node, v))
                    if pair_V[v] == 0:
                        found = True
                        break
                    else:
                        stack.append((pair_V[v], iter(adj[pair_V[v]])))
            except StopIteration:
                stack.pop()
                if not found:
                    path = []
                dist[node] = float('inf')
        if found:
            for u, v in path:
                pair_U[u] = v
                pair_V[v] = u
            return True
        return False

    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_adj = [[] for _ in range(N + M + 1)]  # nodes 1..N (spies), N+1..N+M (tasks)
    for s, t in edges:
        if pair_U[s] == t:
            residual_adj[N + t].append(s)
        else:
            residual_adj[s].append(N + t)

    # Kosaraju's algorithm to find SCCs
    def kosaraju(adj, num_nodes):
        visited = [False] * (num_nodes + 1)
        order = []

        for node in range(1, num_nodes + 1):
            if not visited[node]:
                stack = [(node, False)]
                while stack:
                    current, processed = stack.pop()
                    if processed:
                        order.append(current)
                        continue
                    if visited[current]:
                        continue
                    visited[current] = True
                    stack.append((current, True))
                    for neighbor in reversed(adj[current]):
                        if not visited[neighbor]:
                            stack.append((neighbor, False))

        reversed_adj = [[] for _ in range(num_nodes + 1)]
        for u in range(1, num_nodes + 1):
            for v in adj[u]:
                reversed_adj[v].append(u)

        visited = [False] * (num_nodes + 1)
        component = [0] * (num_nodes + 1)
        current_component = 0

        for node in reversed(order):
            if not visited[node]:
                current_component += 1
                stack = [node]
                visited[node] = True
                component[node] = current_component
                while stack:
                    current = stack.pop()
                    for neighbor in reversed_adj[current]:
                        if not visited[neighbor]:
                            visited[neighbor] = True
                            component[neighbor] = current_component
                            stack.append(neighbor)
        return component

    num_nodes = N + M
    component = kosaraju(residual_adj, num_nodes)

    # Process each query
    for s, t in edges:
        if pair_U[s] == t:
            print("Yes")
        else:
            spy_node = s
            task_node = N + t
            if component[spy_node] == component[task_node]:
                print("Yes")
            else:
                print("No")

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