結果

問題 No.1745 Selfish Spies 2 (à la Princess' Perfectionism)
ユーザー lam6er
提出日時 2025-03-20 20:58:38
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,270 bytes
コンパイル時間 239 ms
コンパイル使用メモリ 82,196 KB
実行使用メモリ 162,956 KB
最終ジャッジ日時 2025-03-20 20:59:41
合計ジャッジ時間 21,043 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 20 WA * 23 RE * 16
権限があれば一括ダウンロードができます

ソースコード

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
    edges = []
    adj = [[] for _ in range(N+1)]
    for _ in range(L):
        s = int(input[idx]); idx +=1
        t = int(input[idx]); idx +=1
        edges.append((s, t))
        adj[s].append(t)
    Pair_U = [0]*(N+1)
    Pair_V = [0]*(M+1)
    dist = [0]*(N+1)
    def hopcroft_karp():
        nonlocal N, M, adj, Pair_U, Pair_V, dist
        q = deque()
        result = 0
        while True:
            q.clear()
            dist = [float('inf')]*(N+1)
            for u in range(1, N+1):
                if Pair_U[u] == 0:
                    dist[u] = 0
                    q.append(u)
            dist[0] = float('inf')
            while q:
                u = q.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
                            q.append(Pair_V[v])
            if dist[0] == float('inf'):
                break
            result += sum(1 for u in range(1, N+1) if Pair_U[u] == 0 and dfs(u))
        return result
    def dfs(u):
        for v in adj[u]:
            if dist[Pair_V[v]] == dist[u] + 1 or (dist[Pair_V[v]] == 0 and Pair_V[v] == 0):
                if Pair_V[v] == 0 or dfs(Pair_V[v]):
                    Pair_U[u] = v
                    Pair_V[v] = u
                    return 1
        dist[u] = float('inf')
        return 0
    hopcroft_karp()
    residual_size = N + M
    residual = [[] for _ in range(residual_size + 1)]
    for s, t in edges:
        if Pair_V[t] == s:
            rt = N + t
            residual[rt].append(s)
        else:
            rs = s
            rt = N + t
            residual[rs].append(rt)
    index = 0
    indices = [0]*(residual_size +1)
    low = [0]*(residual_size +1)
    on_stack = [False]*(residual_size +1)
    stack = []
    scc = []
    current_component = [0]*(residual_size +1)
    component_id = 0
    def strongconnect(v):
        nonlocal index, component_id
        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]:
            component_id +=1
            while True:
                w = stack.pop()
                on_stack[w] = False
                current_component[w] = component_id
                if w == v:
                    break
    for v in range(1, residual_size +1):
        if indices[v] ==0:
            strongconnect(v)
    for (s, t) in edges:
        if Pair_V[t] == s:
            print("Yes")
        else:
            u_in_residual = s
            v_in_residual = N + t
            if current_component[u_in_residual] == current_component[v_in_residual]:
                print("Yes")
            else:
                print("No")
if __name__ == "__main__":
    main()
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0