結果

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

ソースコード

diff # 

import sys
from collections import deque

def main():
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx]); idx +=1
    M = int(input[idx]); idx +=1
    L = int(input[idx]); idx +=1

    adj_left = [[] for _ in range(N+1)]
    edges = []
    for _ in range(L):
        s = int(input[idx]); idx +=1
        t = int(input[idx]); idx +=1
        adj_left[s].append(t)
        edges.append((s, t))

    # Hopcroft-Karp algorithm
    match_u = [0]*(N+1)
    match_v = [0]*(M+1)
    dist = [0]*(N+1)

    def bfs():
        queue = deque()
        for u in range(1, N+1):
            if match_u[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_left[u]:
                if dist[match_v[v]] == float('inf'):
                    dist[match_v[v]] = dist[u] + 1
                    queue.append(match_v[v])
        return dist[0] != float('inf')

    def dfs(u):
        if u != 0:
            for v in adj_left[u]:
                if dist[match_v[v]] == dist[u] + 1:
                    if dfs(match_v[v]):
                        match_u[u] = v
                        match_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 match_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_left[u]:
            if match_u[u] != v:
                residual_graph[u].append(N + v)
    for v in range(1, M+1):
        u_match = match_v[v]
        if u_match != 0:
            residual_graph[N + v].append(u_match)

    # Compute SCC using Kosaraju's algorithm
    num_nodes = N + M
    visited = [False] * (num_nodes + 2)
    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 reversed(residual_graph[node]):
                if not visited[v]:
                    stack.append((v, False))

    for u in range(1, num_nodes + 1):
        if not visited[u]:
            dfs1(u)

    reversed_graph = [[] for _ in range(num_nodes + 2)]
    for u in range(1, num_nodes + 1):
        for v in residual_graph[u]:
            reversed_graph[v].append(u)

    visited = [False] * (num_nodes + 2)
    component = [0] * (num_nodes + 2)
    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)

    # Process each edge
    for (s, t) in edges:
        if match_u[s] == t:
            print("Yes")
        else:
            s_node = s
            t_node = N + t
            if component[s_node] == component[t_node]:
                print("Yes")
            else:
                print("No")

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