結果
問題 | No.2505 matriX cOnstRuction |
ユーザー | suisen |
提出日時 | 2023-07-28 20:43:12 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 989 ms / 2,500 ms |
コード長 | 4,143 bytes |
コンパイル時間 | 732 ms |
コンパイル使用メモリ | 87,112 KB |
実行使用メモリ | 201,400 KB |
最終ジャッジ日時 | 2023-10-13 18:19:04 |
合計ジャッジ時間 | 25,504 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 184 ms
186,212 KB |
testcase_01 | AC | 436 ms
193,036 KB |
testcase_02 | AC | 341 ms
189,648 KB |
testcase_03 | AC | 332 ms
189,820 KB |
testcase_04 | AC | 328 ms
189,844 KB |
testcase_05 | AC | 343 ms
190,688 KB |
testcase_06 | AC | 418 ms
190,900 KB |
testcase_07 | AC | 288 ms
188,968 KB |
testcase_08 | AC | 298 ms
189,804 KB |
testcase_09 | AC | 298 ms
189,280 KB |
testcase_10 | AC | 293 ms
189,656 KB |
testcase_11 | AC | 310 ms
188,968 KB |
testcase_12 | AC | 312 ms
189,280 KB |
testcase_13 | AC | 316 ms
189,040 KB |
testcase_14 | AC | 302 ms
189,180 KB |
testcase_15 | AC | 292 ms
188,764 KB |
testcase_16 | AC | 286 ms
188,820 KB |
testcase_17 | AC | 300 ms
189,060 KB |
testcase_18 | AC | 289 ms
189,292 KB |
testcase_19 | AC | 291 ms
188,972 KB |
testcase_20 | AC | 305 ms
188,664 KB |
testcase_21 | AC | 303 ms
189,496 KB |
testcase_22 | AC | 296 ms
189,384 KB |
testcase_23 | AC | 310 ms
189,796 KB |
testcase_24 | AC | 294 ms
189,116 KB |
testcase_25 | AC | 305 ms
190,012 KB |
testcase_26 | AC | 299 ms
189,064 KB |
testcase_27 | AC | 281 ms
189,476 KB |
testcase_28 | AC | 290 ms
189,160 KB |
testcase_29 | AC | 287 ms
188,724 KB |
testcase_30 | AC | 257 ms
188,624 KB |
testcase_31 | AC | 240 ms
188,240 KB |
testcase_32 | AC | 242 ms
188,268 KB |
testcase_33 | AC | 253 ms
188,728 KB |
testcase_34 | AC | 266 ms
189,060 KB |
testcase_35 | AC | 230 ms
188,248 KB |
testcase_36 | AC | 260 ms
189,372 KB |
testcase_37 | AC | 268 ms
189,600 KB |
testcase_38 | AC | 256 ms
188,648 KB |
testcase_39 | AC | 285 ms
188,780 KB |
testcase_40 | AC | 245 ms
188,760 KB |
testcase_41 | AC | 558 ms
201,300 KB |
testcase_42 | AC | 258 ms
188,748 KB |
testcase_43 | AC | 608 ms
198,208 KB |
testcase_44 | AC | 601 ms
201,052 KB |
testcase_45 | AC | 583 ms
197,992 KB |
testcase_46 | AC | 575 ms
201,400 KB |
testcase_47 | AC | 579 ms
197,760 KB |
testcase_48 | AC | 389 ms
198,796 KB |
testcase_49 | AC | 587 ms
201,220 KB |
testcase_50 | AC | 561 ms
201,244 KB |
testcase_51 | AC | 989 ms
195,900 KB |
testcase_52 | AC | 501 ms
197,980 KB |
testcase_53 | AC | 461 ms
201,236 KB |
testcase_54 | AC | 487 ms
197,828 KB |
testcase_55 | AC | 251 ms
188,356 KB |
testcase_56 | AC | 248 ms
188,124 KB |
testcase_57 | AC | 258 ms
188,308 KB |
testcase_58 | AC | 294 ms
189,884 KB |
testcase_59 | AC | 286 ms
189,164 KB |
testcase_60 | AC | 293 ms
189,416 KB |
testcase_61 | AC | 253 ms
188,512 KB |
testcase_62 | AC | 255 ms
188,444 KB |
testcase_63 | AC | 244 ms
188,496 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 は根の分) 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)