結果
問題 | No.2505 matriX cOnstRuction |
ユーザー |
|
提出日時 | 2023-07-27 23:39:52 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,355 ms / 2,500 ms |
コード長 | 4,500 bytes |
コンパイル時間 | 449 ms |
コンパイル使用メモリ | 81,908 KB |
実行使用メモリ | 301,896 KB |
最終ジャッジ日時 | 2024-09-15 14:07:54 |
合計ジャッジ時間 | 30,975 ms |
ジャッジサーバーID (参考情報) |
judge6 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 64 |
ソースコード
# 兄弟節点を作成する解法from itertools import productimport sysfrom typing import Listdef floor_pow2(n: int):"""2 ** (floor(log2(n)))"""x = 1while (x << 1) <= n:x <<= 1return x# nm の最大値MAX_NM = 50000BIT_NUM = 30INF_COST = 1 << 30# -------------- Binary Trie ここから -------------- ## 最大ノード数の見積もり:# - 帰着後の問題の N は高々 3(n+m)# - 1<=n かつ 1<=m かつ nm<=MAX_NM の下で、n+m の最大値は MAX_NM + 1# - 各制約に対して、(根を除いて) 高々 BIT_NUM 個のノードが新たに生成される# ===> 上限を 3*(MAX_NM+1)*BIT_NUM+1 に設定すれば十分 (+1 は根の分)# 兄弟節点を作成する解法では 3. で高々 2*BIT_NUM 個のノードが新たに生成されるので、節点数は高々 3*(MAX_NM+1)*2*BIT_NUM+1 個MAX_NODE_NUM = 3 * (MAX_NM + 1) * 2 * BIT_NUM + 1# Binary Trie の各ノードに持たせるデータ# - child[0][i] = i 番目のノードの左子 (-1 は左子が存在しないことを表す)# - child[1][i] = i 番目のノードの右子 (-1 は右子が存在しないことを表す)# - weight[i] = i 番目のノードとその親を結ぶ辺の重みchild = [[-1] * MAX_NODE_NUM, [-1] * MAX_NODE_NUM]weight = [0] * MAX_NODE_NUM# Binary Trie のノード数node_num = 0def create_node() -> int:global node_num# 新しいノードの IDnew_node = node_num# ★ 以前のテストケースの情報が残っている可能性があるので、初期化child[0][new_node] = -1 # 左子を Null 節点にするchild[1][new_node] = -1 # 右子を Null 節点にするweight[new_node] = 0 # 重みを 0 にするnode_num += 1return new_nodedef clear_trie() -> None:global node_numnode_num = 0# -------------- Binary Trie ここまで -------------- #def solve(n: int, m: int, R: List[int], C: List[int], A: List[List[int]]):for i, j in product(range(n), range(m)):if A[0][0] ^ A[0][j] ^ A[i][0] ^ A[i][j]:print(-1)returnclear_trie()root = create_node()# f(X) += W * [X ^ Y > Z]def add_weight(Y: int, Z: int, W: int):YZ = Y ^ Zcur = root# Binary Trie に Y^Z を追加for bit in reversed(range(BIT_NUM)):edge_label = (YZ >> bit) & 1if child[edge_label][cur] == -1:child[edge_label][cur] = create_node()# 辺重みの更新: 対応する Z の bit が 0 のとき、兄弟節点に +Wif not ((Z >> bit) & 1):edge_label_sibling = edge_label ^ 1if child[edge_label_sibling][cur] == -1:child[edge_label_sibling][cur] = create_node()weight[child[edge_label_sibling][cur]] += Wcur = child[edge_label][cur]for i in range(n):Y = A[0][0] ^ A[i][0]if R[i]:add_weight(Y, 0, 1)add_weight(Y, R[i], 1)add_weight(Y, 2 * floor_pow2(R[i]) - 1, INF_COST)else:add_weight(Y, 0, INF_COST)for j in range(m):Y = A[0][j]if C[j]:add_weight(Y, 0, 1)add_weight(Y, C[j], 1)add_weight(Y, 2 * floor_pow2(C[j]) - 1, INF_COST)else:add_weight(Y, 0, INF_COST)ans = INF_COST# 辺重みを子部分木に伝播しながらコスト計算# ★ Binary Trieの作り方より必ず「親節点のID<子節点のID」が成り立つので、IDを昇順に走査すれば正しく伝播できるfor cur in range(node_num):# nxt: curの子節点for nxt in (child[0][cur], child[1][cur]):if nxt != -1:# 子節点に辺重みを伝播weight[nxt] += weight[cur]else:# 子がいない ==> 子部分木に非零重みの辺が存在しない ==> 子部分木内の全ての葉のコストが確定ans = min(ans, weight[cur])print(ans if ans < INF_COST else -1)if __name__ == '__main__':readline = sys.stdin.readlineT = int(readline())for _ in range(T):n, m = map(int, readline().split())R = list(map(int, readline().split()))C = list(map(int, readline().split()))A = [list(map(int, readline().split())) for _ in range(n)]solve(n, m, R, C, A)