結果

問題 No.1744 Selfish Spies 1 (à la Princess' Perfectionism)
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 14:03:53
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,527 bytes
コンパイル時間 265 ms
コンパイル使用メモリ 82,712 KB
実行使用メモリ 105,100 KB
最終ジャッジ日時 2025-06-12 14:04:36
合計ジャッジ時間 6,066 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 21 WA * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def hopcroft_karp(graph, U, V):
    pair_U = [0] * (U + 1)
    pair_V = [0] * (V + 1)
    dist = [0] * (U + 1)
    
    while True:
        queue = []
        for u in range(1, U+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.pop(0)
            if dist[u] < dist[0]:
                for v in graph[u]:
                    if dist[pair_V[v]] == float('inf'):
                        dist[pair_V[v]] = dist[u] + 1
                        queue.append(pair_V[v])
        
        if dist[0] == float('inf'):
            break
        
        for u in range(1, U+1):
            if pair_U[u] == 0:
                if dfs(u, graph, pair_U, pair_V, dist):
                    pass
    return pair_U, pair_V

def dfs(u, graph, pair_U, pair_V, dist):
    if u != 0:
        for v in graph[u]:
            if dist[pair_V[v]] == dist[u] + 1:
                if dfs(pair_V[v], graph, pair_U, pair_V, dist):
                    pair_U[u] = v
                    pair_V[v] = u
                    return True
        dist[u] = float('inf')
        return False
    return True

def kosaraju(graph, n):
    visited = [False] * (n + 1)
    order = []
    
    def dfs(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 graph[node]:
                if not visited[v]:
                    stack.append( (v, False) )
    
    for u in range(1, n+1):
        if not visited[u]:
            dfs(u)
    
    transpose = [[] for _ in range(n + 1)]
    for u in range(1, n+1):
        for v in graph[u]:
            transpose[v].append(u)
    
    visited = [False] * (n + 1)
    component = [0] * (n + 1)
    current = 0
    
    for u in reversed(order):
        if not visited[u]:
            current += 1
            stack = [u]
            visited[u] = True
            component[u] = current
            while stack:
                node = stack.pop()
                for v in transpose[node]:
                    if not visited[v]:
                        visited[v] = True
                        component[v] = current
                        stack.append(v)
    
    return component

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
    
    edges = []
    graph = [[] for _ in range(N+1)]
    for _ in range(L):
        s = int(input[ptr]); ptr +=1
        t = int(input[ptr]); ptr +=1
        edges.append( (s, t) )
        graph[s].append(t)
    
    pair_U, pair_V = hopcroft_karp(graph, N, M)
    
    residual_graph = [[] for _ in range(N + M + 1)]
    for s, t in edges:
        if pair_U[s] == t:
            residual_graph[N + t].append(s)
        else:
            residual_graph[s].append(N + t)
    
    component = kosaraju(residual_graph, N + M)
    
    for s, t in edges:
        if pair_U[s] == t:
            if component[s] == component[N + t]:
                print("Yes")
            else:
                print("No")
        else:
            print("Yes")

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