結果
| 問題 | No.3724 Domination |
| コンテスト | |
| ユーザー |
 convexineq
|
| 提出日時 | 2026-09-19 13:44:40 |
| 言語 | PyPy3 (7.3.23 + ACL) |
| 結果 |
WA
不安定
|
| 実行時間 | - |
| コード長 | 30,756 bytes |
| 記録 | |
| コンパイル時間 | 628 ms |
| コンパイル使用メモリ | 90,112 KB |
| 実行使用メモリ | 174,884 KB |
| 最終ジャッジ日時 | 2026-09-19 13:45:10 |
| 合計ジャッジ時間 | 26,233 ms |
|
ジャッジサーバーID （参考情報） |
judge4_0 / judge1_0 |
（要ログイン）
| サブタスク | 配点 | 結果 |
|---|---|---|
| 部分点 | 20 % | AC * 7 WA * 1 |
| 満点 | 80 % | AC * 51 WA * 1 |
| 合計 | 2.5 * 0% = 0 点 |
ソースコード
# ===== BEGIN: /Suzlib/python/graph/BipartiteMatching.py =====
# competitive-verifier: TITLE 最大二部マッチング
from random import shuffle
class BipartiteMatching:
"""Kuhn 法を前処理に用いた Hopcroft--Karp 法。初回 solve の計算量は O((V + E) sqrt(V))。
辺番号を維持するため、削除済み辺も内部に保持する。
累積追加辺数を A とすると、辺情報の保持には O(A) の空間を使い、
edges は O(A)、matching_edge_ids は solve 後に O(V + A)、
CSR の再構築は O(V + A) 時間を要する。
"""
def __init__(self, n_left: int, n_right: int) -> None:
"""左右の頂点数を設定し、辺のない二部グラフと空のマッチングを作る。"""
assert 0 <= n_left
assert 0 <= n_right
self.n_left = n_left
self.n_right = n_right
self.g: list[list[int]] | None = None
self.mate_left = [-1] * n_left
self.mate_right = [-1] * n_right
self.size = 0
self._edge_shift = max(1, (n_right - 1).bit_length())
self._edge_mask = (1 << self._edge_shift) - 1
self._edges: list[int] = []
self._removed_edges: set[int] = set()
self._start: list[int] = []
self._to: list[int] = []
self._csr_built = False
self._solved = False
def add_edge(self, left: int, right: int) -> int:
"""solve 前に左頂点 left と右頂点 right を結ぶ辺を追加し、辺番号を返す。"""
if self._solved:
raise RuntimeError("call add_edge() before solve()")
assert 0 <= left < self.n_left
assert 0 <= right < self.n_right
edge_id = len(self._edges)
self._edges.append((left << self._edge_shift) | right)
return edge_id
def edge_count(self) -> int:
"""これまでに発行した辺番号の個数を返す。削除済み辺も数える。"""
return len(self._edges)
def edges(self) -> list[tuple[int, int, int]]:
"""現在存在する辺を (edge_id, left, right) で返す。"""
shift = self._edge_shift
mask = self._edge_mask
removed = self._removed_edges
return [
(edge_id, edge >> shift, edge & mask)
for edge_id, edge in enumerate(self._edges)
if edge_id not in removed
]
def _build_csr(self) -> None:
"""現在の辺を左頂点ごとの CSR にまとめる。再構築は累積追加辺数 A に対し O(V + A)。"""
if self._csr_built:
return
removed = self._removed_edges
if removed:
edges = [
edge
for edge_id, edge in enumerate(self._edges)
if edge_id not in removed
]
else:
edges = self._edges.copy()
shuffle(edges)
shift = self._edge_shift
mask = self._edge_mask
start = [0] * (self.n_left + 1)
for edge in edges:
start[(edge >> shift) + 1] += 1
for left in range(self.n_left):
start[left + 1] += start[left]
to = [0] * len(edges)
pos = start[:-1]
for edge in edges:
left = edge >> shift
to[pos[left]] = edge & mask
pos[left] += 1
self._start = start
self._to = to
self._csr_built = True
def _materialize_adjacency(self) -> None:
"""更新操作のため、必要になった時だけ可変な隣接リストを生成する。"""
if self.g is not None:
return
self._build_csr()
start = self._start
to = self._to
self.g = [
to[start[left]:start[left + 1]]
for left in range(self.n_left)
]
def _degree_greedy(self) -> int:
"""左右両側の CSR を用いて低次数頂点を優先した初期マッチングを構成する。"""
start = self._start
to = self._to
mate_left = self.mate_left
mate_right = self.mate_right
n_left = self.n_left
n_right = self.n_right
rstart = [0] * (n_right + 1)
for right in to:
rstart[right + 1] += 1
for right in range(n_right):
rstart[right + 1] += rstart[right]
rto = [0] * len(to)
pos = rstart[:-1]
for left in range(n_left):
for i in range(start[left], start[left + 1]):
right = to[i]
rto[pos[right]] = left
pos[right] += 1
degree_left = [start[left + 1] - start[left] for left in range(n_left)]
degree_right = [rstart[right + 1] - rstart[right] for right in range(n_right)]
leaves = [left for left in range(n_left) if degree_left[left] == 1]
leaves += [n_left + right for right in range(n_right) if degree_right[right] == 1]
twos = [left for left in range(n_left) if degree_left[left] == 2]
twos += [n_left + right for right in range(n_right) if degree_right[right] == 2]
added = 0
scan = 0
m = len(to)
while True:
while leaves:
v = leaves[-1]
degree = degree_left[v] if v < n_left else degree_right[v - n_left]
if degree == 1:
break
leaves.pop()
if leaves:
v = leaves.pop()
if v < n_left:
left = v
right = -1
for i in range(start[left], start[left + 1]):
w = to[i]
if degree_right[w]:
right = w
break
else:
right = v - n_left
left = -1
for i in range(rstart[right], rstart[right + 1]):
w = rto[i]
if degree_left[w]:
left = w
break
else:
while scan < n_left and degree_left[scan] == 0:
scan += 1
if scan == n_left:
break
while twos:
v = twos[-1]
degree = degree_left[v] if v < n_left else degree_right[v - n_left]
if degree == 2:
break
twos.pop()
v = twos.pop() if twos else scan
if v < n_left:
left = v
right = -1
best = m + 1
for i in range(start[left], start[left + 1]):
w = to[i]
degree = degree_right[w]
if 0 < degree < best:
right = w
best = degree
else:
right = v - n_left
left = -1
best = m + 1
for i in range(rstart[right], rstart[right + 1]):
w = rto[i]
degree = degree_left[w]
if 0 < degree < best:
left = w
best = degree
if left == -1 or right == -1:
continue
mate_left[left] = right
mate_right[right] = left
added += 1
degree_left[left] = 0
degree_right[right] = 0
for i in range(start[left], start[left + 1]):
w = to[i]
if degree_right[w]:
degree_right[w] -= 1
if degree_right[w] == 1:
leaves.append(n_left + w)
elif degree_right[w] == 2:
twos.append(n_left + w)
for i in range(rstart[right], rstart[right + 1]):
w = rto[i]
if degree_left[w]:
degree_left[w] -= 1
if degree_left[w] == 1:
leaves.append(w)
elif degree_left[w] == 2:
twos.append(w)
return added
def solve(self) -> int:
"""現在のグラフの最大マッチング数を返す。"""
if self._solved:
return self.size
self._build_csr()
start = self._start
to = self._to
mate_left = self.mate_left
mate_right = self.mate_right
if self.size == 0:
self.size = self._degree_greedy()
if self.size == 0:
self._solved = True
return 0
if self.size == min(self.n_left, self.n_right):
self._solved = True
return self.size
parent = [-1] * self.n_left
root = [-1] * self.n_left
queue = [0] * self.n_left
def kuhn_phase() -> int:
"""全未マッチ左頂点から交互森を伸ばし、増大路を貪欲に反転する。"""
q_tail = 0
for left in range(self.n_left):
parent[left] = -1
if mate_left[left] == -1:
parent[left] = -2
root[left] = left
queue[q_tail] = left
q_tail += 1
added = 0
q_front = 0
while q_front < q_tail:
left = queue[q_front]
q_front += 1
if mate_left[root[left]] != -1:
continue
matched_right = mate_left[left]
for i in range(start[left], start[left + 1]):
right = to[i]
if right == matched_right:
continue
next_left = mate_right[right]
if next_left == -1:
while left >= 0:
mate_right[right] = left
right, mate_left[left] = mate_left[left], right
left = parent[left]
added += 1
break
if parent[next_left] == -1:
parent[next_left] = left
root[next_left] = root[left]
queue[q_tail] = next_left
q_tail += 1
return added
for _ in range(128):
added = kuhn_phase()
self.size += added
if added == 0 or self.size == min(self.n_left, self.n_right):
self._solved = True
return self.size
del parent, root, queue
inf = self.n_left + 1
dist = [inf] * self.n_left
current_edge: list[int] = []
def bfs() -> int:
"""未マッチ左頂点から BFS し、最短増大路の長さを返す。"""
queue: list[int] = []
for left in range(self.n_left):
if mate_left[left] == -1:
dist[left] = 0
queue.append(left)
else:
dist[left] = inf
q_front = 0
while q_front < len(queue):
left = queue[q_front]
q_front += 1
next_dist = dist[left] + 1
for i in range(start[left], start[left + 1]):
right = to[i]
next_left = mate_right[right]
if next_left == -1:
return next_dist
if dist[next_left] == inf:
dist[next_left] = next_dist
queue.append(next_left)
return inf
def dfs(start_left: int, shortest: int) -> bool:
"""BFS 層に沿って最短増大路を1本探し、見つかれば反転する。"""
left = start_left
left_stack: list[int] = []
while True:
i = current_edge[left]
end = start[left + 1]
target = dist[left] + 1
while i < end:
right = to[i]
i += 1
next_left = mate_right[right]
if next_left == -1:
if target != shortest:
continue
current_edge[left] = i
while True:
mate_right[right] = left
right, mate_left[left] = mate_left[left], right
if right == -1:
return True
left = left_stack.pop()
if dist[next_left] == target:
current_edge[left] = i
left_stack.append(left)
left = next_left
break
else:
current_edge[left] = i
dist[left] = inf
if not left_stack:
return False
left = left_stack.pop()
while True:
shortest = bfs()
if shortest == inf:
break
current_edge = start[:-1]
for left in range(self.n_left):
if mate_left[left] == -1 and dfs(left, shortest):
self.size += 1
self._solved = True
return self.size
def _augment_once(self) -> bool:
"""全ての未マッチ左頂点から交互 BFS を1回だけ行い、増大路を1本だけ反転する。"""
self._materialize_adjacency()
assert self.g is not None
g = self.g
mate_left = self.mate_left
mate_right = self.mate_right
queue: list[int] = []
parent = [-1] * self.n_left
seen = [False] * self.n_left
for left in range(self.n_left):
if mate_left[left] == -1:
seen[left] = True
queue.append(left)
q_front = 0
while q_front < len(queue):
left = queue[q_front]
q_front += 1
matched_right = mate_left[left]
for right in g[left]:
if right == matched_right:
continue
next_left = mate_right[right]
if next_left == -1:
while right != -1:
mate_right[right] = left
right, mate_left[left] = mate_left[left], right
left = parent[left]
self.size += 1
return True
if not seen[next_left]:
seen[next_left] = True
parent[next_left] = left
queue.append(next_left)
return False
def increment_edge(self, left: int, right: int) -> bool:
"""最大マッチング構築後に辺を1本追加し、サイズが増えたかを返す。"""
if not self._solved:
raise RuntimeError("call solve() before increment_edge()")
assert 0 <= left < self.n_left
assert 0 <= right < self.n_right
self._materialize_adjacency()
assert self.g is not None
self._edges.append((left << self._edge_shift) | right)
self.g[left].append(right)
self._csr_built = False
if self.size == min(self.n_left, self.n_right):
return False
if self.mate_left[left] == -1 and self.mate_right[right] == -1:
self.mate_left[left] = right
self.mate_right[right] = left
self.size += 1
return True
return self._augment_once()
def increment_edges_from_left(self, left: int, rights: list[int]) -> bool:
"""最大マッチング構築後に一つの左頂点から複数辺を追加し、サイズが増えたかを返す。"""
if not self._solved:
raise RuntimeError("call solve() before increment_edges_from_left()")
assert 0 <= left < self.n_left
for right in rights:
assert 0 <= right < self.n_right
self._materialize_adjacency()
assert self.g is not None
base = left << self._edge_shift
self._edges.extend(base | right for right in rights)
self.g[left].extend(rights)
self._csr_built = False
if self.size == min(self.n_left, self.n_right):
return False
if self.mate_left[left] == -1:
for right in rights:
if self.mate_right[right] == -1:
self.mate_left[left] = right
self.mate_right[right] = left
self.size += 1
return True
return self._augment_once()
def increment_edges_from_right(self, right: int, lefts: list[int]) -> bool:
"""最大マッチング構築後に一つの右頂点へ複数辺を追加し、サイズが増えたかを返す。"""
if not self._solved:
raise RuntimeError("call solve() before increment_edges_from_right()")
assert 0 <= right < self.n_right
for left in lefts:
assert 0 <= left < self.n_left
self._materialize_adjacency()
assert self.g is not None
for left in lefts:
self._edges.append((left << self._edge_shift) | right)
self.g[left].append(right)
self._csr_built = False
if self.size == min(self.n_left, self.n_right):
return False
if self.mate_right[right] == -1:
for left in lefts:
if self.mate_left[left] == -1:
self.mate_left[left] = right
self.mate_right[right] = left
self.size += 1
return True
return self._augment_once()
def remove_edge(self, edge_id: int) -> bool:
"""最大マッチング構築後に辺番号 edge_id の辺を削除し、最大マッチング数が減ったかを返す。"""
if not self._solved:
raise RuntimeError("call solve() before remove_edge()")
assert 0 <= edge_id < len(self._edges)
if edge_id in self._removed_edges:
raise ValueError("edge is already removed")
self._materialize_adjacency()
assert self.g is not None
edge = self._edges[edge_id]
left = edge >> self._edge_shift
right = edge & self._edge_mask
self._removed_edges.add(edge_id)
self.g[left].remove(right)
self._csr_built = False
if self.mate_left[left] != right:
return False
self.mate_left[left] = -1
self.mate_right[right] = -1
self.size -= 1
return not self._augment_once()
def matching_edges(self) -> list[tuple[int, int]]:
"""最大マッチングに使われる (左頂点, 右頂点) を返す。"""
self.solve()
return [
(left, right)
for left, right in enumerate(self.mate_left)
if right != -1
]
def matching_edge_ids(self) -> list[int]:
"""最大マッチングに対応する入力辺番号を返す。多重辺では最初の辺を選ぶ。"""
self.solve()
edge_for_left = [-1] * self.n_left
shift = self._edge_shift
mask = self._edge_mask
removed = self._removed_edges
for edge_id, edge in enumerate(self._edges):
if edge_id in removed:
continue
left = edge >> shift
if edge_for_left[left] != -1:
continue
right = edge & mask
if self.mate_left[left] == right:
edge_for_left[left] = edge_id
return [edge_id for edge_id in edge_for_left if edge_id != -1]
def mates(self) -> tuple[list[int], list[int]]:
"""左から右、右から左への対応をそれぞれ返す。未対応は -1。"""
self.solve()
return self.mate_left.copy(), self.mate_right.copy()
def residual_graph(self, middle_capacity_inf: bool = False) -> list[list[int]]:
"""
最大マッチングを s -> left -> right -> t のフローと見た残余グラフを返す。
頂点番号は左 0..n_left-1、右 n_left..n_left+n_right-1、
s = n_left+n_right、t = s+1 とする。
middle_capacity_inf=True なら left -> right の容量を inf とみなす。
"""
self.solve()
n_left = self.n_left
n_right = self.n_right
s = n_left + n_right
t = s + 1
g = [[] for _ in range(t + 1)]
for left, right in enumerate(self.mate_left):
if right == -1:
g[s].append(left)
else:
g[left].append(s)
matched = set(self.matching_edge_ids())
for edge_id, left, right in self.edges():
r = n_left + right
if middle_capacity_inf or edge_id not in matched:
g[left].append(r)
if edge_id in matched:
g[r].append(left)
for right, left in enumerate(self.mate_right):
r = n_left + right
if left == -1:
g[r].append(t)
else:
g[t].append(r)
return g
def _reachable_sets(self) -> tuple[list[bool], list[bool]]:
"""未マッチ左頂点から交互路で到達可能な左右の頂点集合を返す。"""
self.solve()
self._build_csr()
start = self._start
to = self._to
seen_left = [False] * self.n_left
seen_right = [False] * self.n_right
queue: list[int] = []
for left in range(self.n_left):
if self.mate_left[left] == -1:
seen_left[left] = True
queue.append(left)
q_front = 0
while q_front < len(queue):
left = queue[q_front]
q_front += 1
matched_right = self.mate_left[left]
for i in range(start[left], start[left + 1]):
right = to[i]
if right == matched_right or seen_right[right]:
continue
seen_right[right] = True
next_left = self.mate_right[right]
if next_left != -1 and not seen_left[next_left]:
seen_left[next_left] = True
queue.append(next_left)
return seen_left, seen_right
def min_vertex_cover(self) -> tuple[list[int], list[int]]:
"""最小頂点被覆を (左頂点列, 右頂点列) で返す。"""
seen_left, seen_right = self._reachable_sets()
left = [v for v in range(self.n_left) if not seen_left[v]]
right = [v for v in range(self.n_right) if seen_right[v]]
return left, right
def max_independent_set(self) -> tuple[list[int], list[int]]:
"""最大独立集合を (左頂点列, 右頂点列) で返す。"""
seen_left, seen_right = self._reachable_sets()
left = [v for v in range(self.n_left) if seen_left[v]]
right = [v for v in range(self.n_right) if not seen_right[v]]
return left, right
class GeneralBipartiteMatching:
"""頂点を一つの整数空間で与え、自動で二部彩色する最大二部マッチング。"""
def __init__(self, n: int) -> None:
"""n 頂点の空の辺列と、未彩色・未マッチの状態を初期化する。"""
assert 0 <= n
self.n = n
self.edges: list[tuple[int, int]] = []
self.color = [-1] * n
self.toL = [-1] * n
self.toR = [-1] * n
self.fromL: list[int] = []
self.fromR: list[int] = []
self.mateL: list[int] = []
self.mateR: list[int] = []
self.mate = [-1] * n
self.size = 0
self._matching: BipartiteMatching | None = None
self._solved = False
def add_edge(self, u: int, v: int) -> int:
"""頂点 u, v を結ぶ辺を追加し、辺番号を返す。solve 後は彩色を含めて再構築する。"""
assert 0 <= u < self.n
assert 0 <= v < self.n
edge_id = len(self.edges)
self.edges.append((u, v))
self._solved = False
return edge_id
def _bipartition(self) -> None:
"""現在の辺集合を二部彩色し、各頂点の色を self.color に保存する。"""
graph = [[] for _ in range(self.n)]
for u, v in self.edges:
graph[u].append(v)
graph[v].append(u)
color = [-1] * self.n
for start in range(self.n):
if color[start] != -1:
continue
color[start] = 1
queue = [start]
q_front = 0
while q_front < len(queue):
u = queue[q_front]
q_front += 1
next_color = color[u] ^ 1
for v in graph[u]:
if color[v] == -1:
color[v] = next_color
queue.append(v)
elif color[v] != next_color:
raise ValueError("graph is not bipartite")
self.color = color
def _build_lr(self) -> None:
"""二部彩色を左右に圧縮し、内部の BipartiteMatching を構築する。"""
self._bipartition()
self.fromL = [v for v in range(self.n) if self.color[v] == 0]
self.fromR = [v for v in range(self.n) if self.color[v] == 1]
self.toL = [-1] * self.n
self.toR = [-1] * self.n
for left, v in enumerate(self.fromL):
self.toL[v] = left
for right, v in enumerate(self.fromR):
self.toR[v] = right
matching = BipartiteMatching(len(self.fromL), len(self.fromR))
packed_edges: list[int] = []
shift = matching._edge_shift
for u, v in self.edges:
if self.color[u] == 0:
left = self.toL[u]
right = self.toR[v]
else:
left = self.toL[v]
right = self.toR[u]
packed_edges.append((left << shift) | right)
matching._edges = packed_edges
self._matching = matching
def solve(self) -> int:
"""現在のグラフの最大マッチング数を返す。非二部グラフなら ValueError。"""
if self._solved:
return self.size
self._build_lr()
assert self._matching is not None
self.size = self._matching.solve()
self.mateL = self._matching.mate_left
self.mateR = self._matching.mate_right
self.mate = [-1] * self.n
for left, right in enumerate(self.mateL):
if right == -1:
continue
u = self.fromL[left]
v = self.fromR[right]
self.mate[u] = v
self.mate[v] = u
self._solved = True
return self.size
def matching_edges(self) -> list[tuple[int, int]]:
"""最大マッチングを (色0の頂点, 色1の頂点) の組で返す。"""
self.solve()
return [
(self.fromL[left], self.fromR[right])
for left, right in enumerate(self.mateL)
if right != -1
]
def matching_edge_ids(self) -> list[int]:
"""最大マッチングに対応する入力辺番号を返す。多重辺では最初の辺を選ぶ。"""
self.solve()
assert self._matching is not None
return self._matching.matching_edge_ids()
def mates(self) -> list[int]:
"""各頂点の対応先を返す。未対応は -1。"""
self.solve()
return self.mate.copy()
def residual_graph(self, middle_capacity_inf: bool = False) -> list[list[int]]:
"""
自動二部彩色で color 0 を左、color 1 を右とした残余グラフを返す。
頂点番号は入力時の 0..n-1 を保ち、s = n、t = n+1 とする。
middle_capacity_inf=True なら左から右への容量を inf とみなす。
"""
self.solve()
assert self._matching is not None
rg = self._matching.residual_graph(middle_capacity_inf)
original = self.fromL + self.fromR
internal_s = self.n
internal_t = self.n + 1
original += [internal_s, internal_t]
g = [[] for _ in range(self.n + 2)]
for v, adj in enumerate(rg):
g[original[v]] = [original[w] for w in adj]
return g
def min_vertex_cover(self) -> list[int]:
"""元の頂点番号で最小頂点被覆を返す。"""
self.solve()
assert self._matching is not None
left, right = self._matching.min_vertex_cover()
return [self.fromL[v] for v in left] + [self.fromR[v] for v in right]
def max_independent_set(self) -> list[int]:
"""元の頂点番号で最大独立集合を返す。"""
self.solve()
assert self._matching is not None
left, right = self._matching.max_independent_set()
return [self.fromL[v] for v in left] + [self.fromR[v] for v in right]
# ===== END: /Suzlib/python/graph/BipartiteMatching.py =====
import sys
readline = sys.stdin.readline
# T = int(readline())
# for _ in range(T):
# ans = solve()
# print(ans)
# n = int(readline())
# a = [int(i) for i in readline().split()]
# ab = [[int(i) for i in readline().split()] for _ in range()]
# S = readline().strip()
# b = [readline().strip() for _ in range()]
def solve(n,R,C):
if n == 2:
return None
b = [[v]*n for v in R]
x = C[0]
if all(v == x for v in C): # 全部同じなら、ダメなことがある
if n <= 4:
return None
j = 0
for i in range(n):
while b[j][i] == x:
j += 1
if j >= n: j = 0
b[j][i] = x
j += 1
if j >= n: j = 0
return b
# そうでないならマッチング可能
g = BipartiteMatching(n,n)
for i in range(n):
for j in range(n):
if R[i] != C[j]:
g.add_edge(i,j)
g.solve()
lst = g.matching_edges()
for v,w in lst:
b[v][w] = C[w]
#print(lst)
return b
T = int(readline())
for _ in range(T):
n = int(readline())
R = [int(i) for i in readline().split()]
C = [int(i) for i in readline().split()]
ans = solve(n,R,C)
if not ans:
print(-1)
else:
for lst in ans:
print(*lst)