結果

問題 No.2505 matriX cOnstRuction
ユーザー suisensuisen
提出日時 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 246 ms
281,472 KB
testcase_01 AC 526 ms
293,464 KB
testcase_02 AC 441 ms
293,236 KB
testcase_03 AC 424 ms
292,456 KB
testcase_04 AC 425 ms
291,448 KB
testcase_05 AC 439 ms
292,092 KB
testcase_06 AC 530 ms
293,524 KB
testcase_07 AC 357 ms
291,480 KB
testcase_08 AC 359 ms
291,864 KB
testcase_09 AC 355 ms
290,732 KB
testcase_10 AC 362 ms
291,112 KB
testcase_11 AC 362 ms
291,340 KB
testcase_12 AC 367 ms
291,612 KB
testcase_13 AC 363 ms
291,488 KB
testcase_14 AC 366 ms
292,116 KB
testcase_15 AC 367 ms
290,864 KB
testcase_16 AC 353 ms
291,316 KB
testcase_17 AC 352 ms
291,100 KB
testcase_18 AC 361 ms
291,480 KB
testcase_19 AC 361 ms
291,620 KB
testcase_20 AC 370 ms
291,744 KB
testcase_21 AC 356 ms
291,216 KB
testcase_22 AC 361 ms
291,424 KB
testcase_23 AC 363 ms
291,924 KB
testcase_24 AC 357 ms
291,604 KB
testcase_25 AC 369 ms
291,360 KB
testcase_26 AC 356 ms
291,600 KB
testcase_27 AC 357 ms
291,196 KB
testcase_28 AC 360 ms
292,044 KB
testcase_29 AC 354 ms
291,228 KB
testcase_30 AC 322 ms
290,544 KB
testcase_31 AC 308 ms
290,388 KB
testcase_32 AC 312 ms
290,304 KB
testcase_33 AC 319 ms
290,148 KB
testcase_34 AC 345 ms
291,884 KB
testcase_35 AC 301 ms
291,056 KB
testcase_36 AC 336 ms
291,836 KB
testcase_37 AC 333 ms
291,724 KB
testcase_38 AC 321 ms
290,816 KB
testcase_39 AC 368 ms
291,584 KB
testcase_40 AC 312 ms
291,200 KB
testcase_41 AC 766 ms
301,440 KB
testcase_42 AC 315 ms
291,428 KB
testcase_43 AC 816 ms
296,740 KB
testcase_44 AC 774 ms
301,364 KB
testcase_45 AC 818 ms
296,864 KB
testcase_46 AC 783 ms
301,696 KB
testcase_47 AC 791 ms
297,000 KB
testcase_48 AC 498 ms
301,156 KB
testcase_49 AC 763 ms
301,568 KB
testcase_50 AC 776 ms
301,732 KB
testcase_51 AC 1,355 ms
297,660 KB
testcase_52 AC 658 ms
296,868 KB
testcase_53 AC 650 ms
301,896 KB
testcase_54 AC 661 ms
297,124 KB
testcase_55 AC 345 ms
290,916 KB
testcase_56 AC 325 ms
290,608 KB
testcase_57 AC 331 ms
290,928 KB
testcase_58 AC 374 ms
292,388 KB
testcase_59 AC 354 ms
291,372 KB
testcase_60 AC 369 ms
292,220 KB
testcase_61 AC 321 ms
290,120 KB
testcase_62 AC 323 ms
290,228 KB
testcase_63 AC 327 ms
290,188 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

# 兄弟節点を作成する解法

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) * 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 = 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)):
            edge_label = (YZ >> bit) & 1

            if child[edge_label][cur] == -1:
                child[edge_label][cur] = create_node()

            # 辺重みの更新: 対応する Z の bit が 0 のとき、兄弟節点に +W
            if not ((Z >> bit) & 1):
                edge_label_sibling = edge_label ^ 1
                if child[edge_label_sibling][cur] == -1:
                    child[edge_label_sibling][cur] = create_node()
                weight[child[edge_label_sibling][cur]] += W

            cur = 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.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)
0