結果

問題 No.1745 Selfish Spies 2 (à la Princess' Perfectionism)
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 21:35:56
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,923 bytes
コンパイル時間 299 ms
コンパイル使用メモリ 81,664 KB
実行使用メモリ 107,776 KB
最終ジャッジ日時 2025-06-12 21:38:26
合計ジャッジ時間 17,256 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 20 WA * 19 TLE * 1 -- * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def main():
    sys.setrecursionlimit(1 << 25)
    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 = []
    for _ in range(L):
        s = int(input[ptr])-1; ptr +=1
        t = int(input[ptr])-1 + N; ptr +=1  # missions are nodes N, N+1, ..., N+M-1
        edges.append( (s, t) )

    adj = [[] for _ in range(N + M)]
    for s, t in edges:
        adj[s].append(t)
        adj[t].append(s)

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

    def bfs():
        queue = deque()
        for u in range(N):
            if pair_u[u] == -1:
                dist[u] = 0
                queue.append(u)
            else:
                dist[u] = float('inf')
        dist[N + M -1] = float('inf')
        while queue:
            u = queue.popleft()
            if u != -1:
                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[N + M -1] != float('inf')

    def dfs(u):
        if u != -1:
            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(N):
            if pair_u[u] == -1:
                if dfs(u):
                    result +=1

    in_matching = [False]*(N+M)
    for s in range(N):
        if pair_u[s] != -1:
            t = pair_u[s]
            in_matching[s] = True
            in_matching[t] = True

    residual_adj = [[] for _ in range(N+M)]
    for s, t in edges:
        if pair_u[s] == t and pair_v[t] == s:
            residual_adj[t].append(s)
        else:
            residual_adj[s].append(t)

    reachable = [ set() for _ in range(N+M) ]
    for t in range(N, N+M):
        visited = set()
        queue = deque([t])
        visited.add(t)
        while queue:
            u = queue.popleft()
            for v in residual_adj[u]:
                if v not in visited:
                    visited.add(v)
                    queue.append(v)
        for u in visited:
            if u < N:
                reachable[t].add(u)

    output = []
    for s, t in edges:
        t_node = t
        s_node = s
        if pair_u[s_node] == t_node:
            output.append("Yes")
        else:
            if s_node in reachable[t_node]:
                output.append("Yes")
            else:
                output.append("No")

    print('\n'.join(output))

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