結果
| 問題 |
No.1745 Selfish Spies 2 (à la Princess' Perfectionism)
|
| コンテスト | |
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:20:25 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 7,679 bytes |
| コンパイル時間 | 307 ms |
| コンパイル使用メモリ | 81,920 KB |
| 実行使用メモリ | 303,296 KB |
| 最終ジャッジ日時 | 2025-05-14 13:22:07 |
| 合計ジャッジ時間 | 21,755 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 27 WA * 32 |
ソースコード
import sys
sys.setrecursionlimit(4 * 10**5)
# Max vertices N+M can be 2*10^5. SCC DFS depth can be N+M.
# Hopcroft-Karp DFS depth is O(sqrt(N+M)), much smaller.
# Hopcroft-Karp Algorithm for Maximum Bipartite Matching
# N_spies: number of spies (nodes in U set)
# M_missions: number of missions (nodes in V set)
# adj_list_spies: adjacency list where adj_list_spies[u] is a list of missions spy u can do
def hopcroft_karp_algorithm(N_spies, M_missions, adj_list_spies):
match_U = [-1] * N_spies # match_U[u] = mission matched to spy u, or -1
match_V = [-1] * M_missions # match_V[v] = spy matched to mission v, or -1
# dist_bfs[u] stores distance of spy u from an unmatched spy in current BFS layering
dist_bfs = [-1] * N_spies
matching_count = 0
# BFS part of Hopcroft-Karp
def bfs_hk():
queue = []
for u_spy in range(N_spies):
if match_U[u_spy] == -1: # If spy u_spy is unmatched
queue.append(u_spy)
dist_bfs[u_spy] = 0
else:
dist_bfs[u_spy] = -1 # Mark as not visited / infinite distance
head_ptr = 0
found_augmenting_path_layer = False
while head_ptr < len(queue):
u_spy = queue[head_ptr]
head_ptr += 1
for v_mission in adj_list_spies[u_spy]:
spy_matched_to_v = match_V[v_mission]
if spy_matched_to_v == -1: # Mission v_mission is unmatched
found_augmenting_path_layer = True
# This indicates a layer leading to an unmatched mission is found.
# We don't stop BFS here; we need to layer all reachable spies.
elif dist_bfs[spy_matched_to_v] == -1: # If spy matched to v_mission is not yet layered
dist_bfs[spy_matched_to_v] = dist_bfs[u_spy] + 1
queue.append(spy_matched_to_v)
return found_augmenting_path_layer
# DFS part of Hopcroft-Karp
# Tries to find an augmenting path starting from u_spy using current BFS layers
def dfs_hk(u_spy):
for v_mission in adj_list_spies[u_spy]:
spy_matched_to_v = match_V[v_mission]
if spy_matched_to_v == -1: # Mission v_mission is unmatched, augmenting path found
match_U[u_spy] = v_mission
match_V[v_mission] = u_spy
return True
# If spy_matched_to_v is in the next layer of BFS tree
elif dist_bfs[spy_matched_to_v] == dist_bfs[u_spy] + 1:
if dfs_hk(spy_matched_to_v): # Recursively find path from spy_matched_to_v
match_U[u_spy] = v_mission
match_V[v_mission] = u_spy
return True
# Mark u_spy as visited for this DFS phase by setting its dist to -1 (infinity)
# This ensures u_spy is not part of another augmenting path found in this phase
dist_bfs[u_spy] = -1
return False
# Main loop of Hopcroft-Karp
while bfs_hk(): # While BFS can find layers for augmenting paths
for u_spy in range(N_spies):
if match_U[u_spy] == -1: # If spy u_spy is unmatched
if dfs_hk(u_spy): # Try to find an augmenting path starting from u_spy
matching_count += 1
return match_U, match_V, matching_count
# Kosaraju's Algorithm for SCCs
# num_nodes: total number of nodes in the graph (N_spies + M_missions)
# graph_adj: adjacency list of the graph
# graph_rev_adj: adjacency list of the reversed graph
def kosaraju_scc_algorithm(num_nodes, graph_adj, graph_rev_adj):
visited_nodes = [False] * num_nodes
finish_order_stack = [] # Stack to store nodes by finishing times in first DFS pass
def dfs_pass1(u_node):
visited_nodes[u_node] = True
for v_neighbor in graph_adj[u_node]:
if not visited_nodes[v_neighbor]:
dfs_pass1(v_neighbor)
finish_order_stack.append(u_node)
for i in range(num_nodes):
if not visited_nodes[i]:
dfs_pass1(i)
scc_ids = [-1] * num_nodes # scc_ids[u_node] = ID of SCC containing u_node
current_scc_id_counter = 0
# Reset visited_nodes for second DFS pass on reversed graph
visited_nodes = [False] * num_nodes
def dfs_pass2(u_node, current_scc_id):
visited_nodes[u_node] = True
scc_ids[u_node] = current_scc_id
for v_neighbor in graph_rev_adj[u_node]:
if not visited_nodes[v_neighbor]:
dfs_pass2(v_neighbor, current_scc_id)
while finish_order_stack:
u_node = finish_order_stack.pop()
if not visited_nodes[u_node]:
dfs_pass2(u_node, current_scc_id_counter)
current_scc_id_counter += 1
return scc_ids
def solve():
N, M, L = map(int, sys.stdin.readline().split())
# Store original edges with their input order for output
# Using 0-indexed spy/mission IDs internally
input_edges_data = []
for i in range(L):
s, t = map(int, sys.stdin.readline().split())
input_edges_data.append({'s': s - 1, 't': t - 1, 'original_idx': i})
# Prepare adjacency list for Hopcroft-Karp (spies -> missions)
adj_list_for_hk = [[] for _ in range(N)]
for edge_data in input_edges_data:
adj_list_for_hk[edge_data['s']].append(edge_data['t'])
# 1. Compute Maximum Matching M
match_U, _, _ = hopcroft_karp_algorithm(N, M, adj_list_for_hk)
# 2. Construct Directed Graph D_M
# Nodes: 0 to N-1 for spies, N to N+M-1 for missions
total_nodes_in_D_M = N + M
D_M_adj = [[] for _ in range(total_nodes_in_D_M)]
D_M_rev_adj = [[] for _ in range(total_nodes_in_D_M)]
for edge_data in input_edges_data: # Iterate through all L possible assignments
s_idx = edge_data['s'] # 0-indexed spy ID
t_idx = edge_data['t'] # 0-indexed mission ID
node_s = s_idx # Graph node ID for spy s_idx
node_m = N + t_idx # Graph node ID for mission t_idx
if match_U[s_idx] == t_idx: # If edge (s_idx, t_idx) is in the computed matching M
# Add edge node_m -> node_s in D_M (mission -> spy)
D_M_adj[node_m].append(node_s)
D_M_rev_adj[node_s].append(node_m)
else: # If edge (s_idx, t_idx) is not in M
# Add edge node_s -> node_m in D_M (spy -> mission)
D_M_adj[node_s].append(node_m)
D_M_rev_adj[node_m].append(node_s)
# 3. Find SCCs of D_M
scc_ids_map = kosaraju_scc_algorithm(total_nodes_in_D_M, D_M_adj, D_M_rev_adj)
# 4. Answer Queries
# Preallocate results list to store answers in original query order
query_results = [""] * L
for edge_data in input_edges_data:
s_idx = edge_data['s']
t_idx = edge_data['t']
original_query_idx = edge_data['original_idx']
node_s = s_idx
node_m = N + t_idx
if match_U[s_idx] == t_idx: # Edge is in the computed maximum matching M
query_results[original_query_idx] = "Yes"
else: # Edge is not in M
# Check if node_s and node_m are in the same SCC of D_M
# Also ensure their SCC IDs are valid (not -1, if -1 means node was not processed, though it should be)
if scc_ids_map[node_s] == scc_ids_map[node_m] and scc_ids_map[node_s] != -1:
query_results[original_query_idx] = "Yes"
else:
query_results[original_query_idx] = "No"
sys.stdout.write('\n'.join(query_results) + '\n')
solve()