結果

問題 No.1744 Selfish Spies 1 (à la Princess' Perfectionism)
ユーザー lam6er
提出日時 2025-04-16 16:24:25
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,201 bytes
コンパイル時間 353 ms
コンパイル使用メモリ 82,032 KB
実行使用メモリ 89,880 KB
最終ジャッジ日時 2025-04-16 16:25:27
合計ジャッジ時間 5,318 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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 = [tuple(map(int, sys.stdin.readline().split())) for _ in range(L)]
    
    # Build adjacency list for Hopcroft-Karp
    adj = [[] for _ in range(N+1)]  # Spies are 1-based
    for u, v in edges:
        adj[u].append(v)
    
    # Hopcroft-Karp algorithm to find maximum matching
    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):
        if u != 0:
            for v in adj[u]:
                if dist[pair_v[v]] == dist[u] + 1:
                    if dfs(pair_v[v]):
                        pair_u[u] = v
                        pair_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 pair_u[u] == 0:
                if dfs(u):
                    result += 1
    
    # Build residual graph
    residual = [[] for _ in range(N + M + 1)]  # Spies 1..N, Tasks N+1..N+M
    for u, v in edges:
        if pair_u[u] == v:
            residual[N + v].append(u)
        else:
            residual[u].append(N + v)
    
    # Tarjan's algorithm to find SCCs
    index = 0
    indices = [0] * (N + M + 1)
    low = [0] * (N + M + 1)
    on_stack = [False] * (N + M + 1)
    stack = []
    scc = []
    current_component = 0
    component = [0] * (N + M + 1)
    
    def strongconnect(v):
        nonlocal index, current_component
        index += 1
        indices[v] = index
        low[v] = index
        stack.append(v)
        on_stack[v] = True
        for w in residual[v]:
            if indices[w] == 0:
                strongconnect(w)
                low[v] = min(low[v], low[w])
            elif on_stack[w]:
                low[v] = min(low[v], indices[w])
        if low[v] == indices[v]:
            current_component += 1
            while True:
                w = stack.pop()
                on_stack[w] = False
                component[w] = current_component
                if w == v:
                    break
    
    for v in range(1, N + M + 1):
        if indices[v] == 0:
            strongconnect(v)
    
    # Process each edge
    for u, v in edges:
        if pair_u[u] != v:
            print("Yes")
        else:
            spy_node = u
            task_node = N + v
            if component[spy_node] == component[task_node]:
                print("Yes")
            else:
                print("No")

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