結果

問題 No.1745 Selfish Spies 2 (à la Princess' Perfectionism)
コンテスト
ユーザー lam6er
提出日時 2025-04-09 20:56:29
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,800 bytes
コンパイル時間 223 ms
コンパイル使用メモリ 82,292 KB
実行使用メモリ 159,788 KB
最終ジャッジ日時 2025-04-09 20:58:40
合計ジャッジ時間 23,109 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 27 WA * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def main():
    sys.setrecursionlimit(1 << 25)
    N, M, L = map(int, sys.stdin.readline().split())
    edges = [[] for _ in range(N+1)]  # 1-based for spies
    input_edges = []
    for _ in range(L):
        S, T = map(int, sys.stdin.readline().split())
        input_edges.append((S, T))
        edges[S].append(T)

    # Hopcroft-Karp algorithm to find maximum matching
    spy_to_task = [0]*(N+1)
    task_to_spy = [0]*(M+1)
    dist = [0]*(N+1)

    def bfs():
        queue = deque()
        for s in range(1, N+1):
            if spy_to_task[s] == 0:
                dist[s] = 0
                queue.append(s)
            else:
                dist[s] = float('inf')
        dist[0] = float('inf')
        while queue:
            s = queue.popleft()
            for t in edges[s]:
                if dist[task_to_spy[t]] == float('inf'):
                    dist[task_to_spy[t]] = dist[s] + 1
                    queue.append(task_to_spy[t])
        return dist[0] != float('inf')

    def dfs(s):
        if s != 0:
            for t in edges[s]:
                if dist[task_to_spy[t]] == dist[s] + 1 and dfs(task_to_spy[t]):
                    spy_to_task[s] = t
                    task_to_spy[t] = s
                    return True
            dist[s] = float('inf')
            return False
        return True

    result = 0
    while bfs():
        for s in range(1, N+1):
            if spy_to_task[s] == 0 and dfs(s):
                result += 1

    # Build residual graph
    residual_edges = []
    node_count = N + M
    # Residual graph: Spies are 1..N, tasks are N+1..N+M
    # Adjusting for 0-based in residual graph nodes (0 not used)
    for s in range(1, N+1):
        for t in edges[s]:
            if spy_to_task[s] == t:
                residual_edges.append((N + t, s))  # task to spy (reverse edge)
            else:
                residual_edges.append((s, N + t))  # spy to task (forward edge)

    # Build adjacency list for SCC
    adj = [[] for _ in range(N + M + 2)]  # 1-based to N+M+1
    for u, v in residual_edges:
        adj[u].append(v)

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

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

    adj_rev = [[] for _ in range(N + M + 2)]
    for u, v in residual_edges:
        adj_rev[v].append(u)

    visited = [False] * (N + M + 2)
    scc = [0] * (N + M + 2)
    current_component = 0

    def dfs2(u, label):
        stack = [(u, False)]
        visited[u] = True
        scc[u] = label
        while stack:
            node, processed = stack.pop()
            if processed:
                continue
            for v in adj_rev[node]:
                if not visited[v]:
                    visited[v] = True
                    scc[v] = label
                    stack.append((v, False))
    for u in reversed(order):
        if not visited[u]:
            current_component += 1
            dfs2(u, current_component)

    # Process each query
    for S, T in input_edges:
        if spy_to_task[S] == T:
            print("Yes")
        else:
            s_node = S
            t_node = N + T
            if scc[s_node] == scc[t_node]:
                print("Yes")
            else:
                print("No")

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