結果

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

ソースコード

diff # 

import sys
from collections import deque

def main():
    sys.setrecursionlimit(1 << 25)
    N, M, L = map(int, sys.stdin.readline().split())
    edges = []
    adj = [[] for _ in range(N+1)]  # adj[u] for u in 1..N
    for _ in range(L):
        s, t = map(int, sys.stdin.readline().split())
        edges.append((s, t))
        adj[s].append(t)
    
    # Hopcroft-Karp algorithm to find maximum bipartite matching
    left_matched = [0] * (N + 1)
    right_matched = [0] * (M + 1)
    dist = [0] * (N + 1)

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

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

    result = 0
    while bfs():
        for u in range(1, N + 1):
            if left_matched[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 left_matched[s] == t:
            residual_adj[N + t].append(s)
        else:
            residual_adj[s].append(N + t)
    
    # Kosaraju's algorithm to find SCCs
    visited = [False] * (N + M + 1)
    order = []
    def dfs1(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 residual_adj[node]:
                if not visited[v]:
                    stack.append((v, False))
    for u in range(1, N + M + 1):
        if not visited[u]:
            dfs1(u)
    
    reverse_adj = [[] for _ in range(N + M + 1)]
    for u in range(1, N + M + 1):
        for v in residual_adj[u]:
            reverse_adj[v].append(u)
    
    visited = [False] * (N + M + 1)
    component = [0] * (N + M + 1)
    current_component = 0
    for u in reversed(order):
        if not visited[u]:
            current_component += 1
            stack = [u]
            visited[u] = True
            component[u] = current_component
            while stack:
                node = stack.pop()
                for v in reverse_adj[node]:
                    if not visited[v]:
                        visited[v] = True
                        component[v] = current_component
                        stack.append(v)
    
    # Process each edge to determine the answer
    for s, t in edges:
        if left_matched[s] == t:
            if component[s] == component[N + t]:
                print("Yes")
            else:
                print("No")
        else:
            print("Yes")

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