結果
問題 | No.2505 matriX cOnstRuction |
ユーザー | suisen |
提出日時 | 2023-07-27 23:38:55 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 995 ms / 2,500 ms |
コード長 | 4,308 bytes |
コンパイル時間 | 1,787 ms |
コンパイル使用メモリ | 86,228 KB |
実行使用メモリ | 201,316 KB |
最終ジャッジ日時 | 2023-10-13 18:18:12 |
合計ジャッジ時間 | 28,796 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 217 ms
185,920 KB |
testcase_01 | AC | 570 ms
192,808 KB |
testcase_02 | AC | 375 ms
189,724 KB |
testcase_03 | AC | 365 ms
189,536 KB |
testcase_04 | AC | 369 ms
189,400 KB |
testcase_05 | AC | 368 ms
190,528 KB |
testcase_06 | AC | 445 ms
190,796 KB |
testcase_07 | AC | 304 ms
188,880 KB |
testcase_08 | AC | 323 ms
190,004 KB |
testcase_09 | AC | 313 ms
189,356 KB |
testcase_10 | AC | 305 ms
189,008 KB |
testcase_11 | AC | 334 ms
189,256 KB |
testcase_12 | AC | 301 ms
188,832 KB |
testcase_13 | AC | 290 ms
188,904 KB |
testcase_14 | AC | 291 ms
189,124 KB |
testcase_15 | AC | 284 ms
188,792 KB |
testcase_16 | AC | 282 ms
189,180 KB |
testcase_17 | AC | 292 ms
188,848 KB |
testcase_18 | AC | 294 ms
189,004 KB |
testcase_19 | AC | 296 ms
188,904 KB |
testcase_20 | AC | 285 ms
188,748 KB |
testcase_21 | AC | 304 ms
189,608 KB |
testcase_22 | AC | 294 ms
189,180 KB |
testcase_23 | AC | 320 ms
189,944 KB |
testcase_24 | AC | 286 ms
188,952 KB |
testcase_25 | AC | 301 ms
190,324 KB |
testcase_26 | AC | 289 ms
189,036 KB |
testcase_27 | AC | 289 ms
189,188 KB |
testcase_28 | AC | 287 ms
188,980 KB |
testcase_29 | AC | 291 ms
188,640 KB |
testcase_30 | AC | 252 ms
188,336 KB |
testcase_31 | AC | 243 ms
188,504 KB |
testcase_32 | AC | 242 ms
188,116 KB |
testcase_33 | AC | 249 ms
188,696 KB |
testcase_34 | AC | 273 ms
188,740 KB |
testcase_35 | AC | 235 ms
188,568 KB |
testcase_36 | AC | 281 ms
189,448 KB |
testcase_37 | AC | 264 ms
189,384 KB |
testcase_38 | AC | 247 ms
188,572 KB |
testcase_39 | AC | 284 ms
188,764 KB |
testcase_40 | AC | 237 ms
188,696 KB |
testcase_41 | AC | 586 ms
201,316 KB |
testcase_42 | AC | 238 ms
188,816 KB |
testcase_43 | AC | 599 ms
198,164 KB |
testcase_44 | AC | 575 ms
201,104 KB |
testcase_45 | AC | 624 ms
197,780 KB |
testcase_46 | AC | 692 ms
201,168 KB |
testcase_47 | AC | 728 ms
197,924 KB |
testcase_48 | AC | 455 ms
198,800 KB |
testcase_49 | AC | 695 ms
201,244 KB |
testcase_50 | AC | 695 ms
201,136 KB |
testcase_51 | AC | 995 ms
195,828 KB |
testcase_52 | AC | 488 ms
197,848 KB |
testcase_53 | AC | 476 ms
201,312 KB |
testcase_54 | AC | 485 ms
197,672 KB |
testcase_55 | AC | 257 ms
188,108 KB |
testcase_56 | AC | 259 ms
188,080 KB |
testcase_57 | AC | 251 ms
188,200 KB |
testcase_58 | AC | 305 ms
190,164 KB |
testcase_59 | AC | 276 ms
188,936 KB |
testcase_60 | AC | 277 ms
189,228 KB |
testcase_61 | AC | 252 ms
188,340 KB |
testcase_62 | AC | 275 ms
187,940 KB |
testcase_63 | AC | 251 ms
188,312 KB |
ソースコード
# 兄弟節点を作成しない解法 from itertools import product import sys from typing import List def floor_pow2(n: int): """ 2 ** (floor(log2(n))) """ x = 1 while (x << 1) <= n: x <<= 1 return x # nm の最大値 MAX_NM = 50000 BIT_NUM = 30 INF_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) * 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 = 0 def create_node() -> int: global node_num # 新しいノードの ID new_node = node_num # ★ 以前のテストケースの情報が残っている可能性があるので、初期化 child[0][new_node] = -1 # 左子を Null 節点にする child[1][new_node] = -1 # 右子を Null 節点にする weight[new_node] = 0 # 重みを 0 にする node_num += 1 return new_node def clear_trie() -> None: global node_num node_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) return clear_trie() root = create_node() # f(X) += W * [X ^ Y > Z] def add_weight(Y: int, Z: int, W: int): YZ = Y ^ Z cur = root # Binary Trie に Y^Z を追加 for bit in reversed(range(BIT_NUM)): ch = child[(YZ >> bit) & 1] if ch[cur] == -1: ch[cur] = create_node() nxt = ch[cur] # 辺重みの更新: 対応する Z の bit が 0 のとき、親に +W, 自分に -W if not ((Z >> bit) & 1): weight[cur] += W weight[nxt] -= W cur = nxt 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.readline T = 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)