checksum.cpp

#include<bits/stdc++.h>

template <typename T, int NDIMS> struct tensor_view {
    static_assert(NDIMS >= 0, "NDIMS must be nonnegative");

protected:
    std::array<int, NDIMS> shape;
    std::array<int, NDIMS> strides;
    T* data;

    tensor_view(std::array<int, NDIMS> shape_, std::array<int, NDIMS> strides_, T* data_) : shape(shape_), strides(strides_), data(data_) {}

public:
    tensor_view() : shape{0}, strides{0}, data(nullptr) {}

protected:
    int flatten_index(std::array<int, NDIMS> idx) const {
        int res = 0;
        for (int i = 0; i < NDIMS; i++) { res += idx[i] * strides[i]; }
        return res;
    }
    int flatten_index_checked(std::array<int, NDIMS> idx) const {
        int res = 0;
        for (int i = 0; i < NDIMS; i++) {
            assert(0 <= idx[i] && idx[i] < shape[i]);
            res += idx[i] * strides[i];
        }
        return res;
    }

public:
    T& operator[] (std::array<int, NDIMS> idx) const {
        return data[flatten_index(idx)];
    }
    T& at(std::array<int, NDIMS> idx) const {
        return data[flatten_index_checked(idx)];
    }

    template <int D = NDIMS>
    typename std::enable_if<(0 < D), tensor_view<T, NDIMS-1>>::type operator[] (int idx) const {
        std::array<int, NDIMS-1> nshape; std::copy(shape.begin()+1, shape.end(), nshape.begin());
        std::array<int, NDIMS-1> nstrides; std::copy(strides.begin()+1, strides.end(), nstrides.begin());
        T* ndata = data + (strides[0] * idx);
        return tensor_view<T, NDIMS-1>(nshape, nstrides, ndata);
    }
    template <int D = NDIMS>
    typename std::enable_if<(0 < D), tensor_view<T, NDIMS-1>>::type at(int idx) const {
        assert(0 <= idx && idx < shape[0]);
        return operator[](idx);
    }

    template <int D = NDIMS>
    typename std::enable_if<(0 == D), T&>::type operator * () const {
        return *data;
    }

    template <typename U, int D> friend struct tensor_view;
    template <typename U, int D> friend struct tensor;
};

template <typename T, int NDIMS> struct tensor {
    static_assert(NDIMS >= 0, "NDIMS must be nonnegative");

protected:
    std::array<int, NDIMS> shape;
    std::array<int, NDIMS> strides;
    int len;
    T* data;

public:
    tensor() : shape{0}, strides{0}, len(0), data(nullptr) {}

    explicit tensor(std::array<int, NDIMS> shape_, const T& t = T()) {
        shape = shape_;
        strides[NDIMS-1] = 1;
        for (int i = NDIMS-1; i > 0; i--) {
            strides[i-1] = strides[i] * shape[i];
        }
        len = strides[0] * shape[0];
        data = new T[len];
        std::fill(data, data + len, t);
    }

    tensor(const tensor& o) : shape(o.shape), strides(o.strides), len(o.len), data(new T[len]) {
        for (int i = 0; i < len; i++) {
            data[i] = o.data[i];
        }
    }

    tensor& operator=(tensor&& o) noexcept {
        using std::swap;
        swap(shape, o.shape);
        swap(strides, o.strides);
        swap(len, o.len);
        swap(data, o.data);
        return *this;
    }
    tensor(tensor&& o) : tensor() {
        *this = std::move(o);
    }
    tensor& operator=(const tensor& o) {
        return *this = tensor(o);
    }
    ~tensor() { delete[] data; }

    using view_t = tensor_view<T, NDIMS>;
    view_t view() {
        return tensor_view<T, NDIMS>(shape, strides, data);
    }
    operator view_t() {
        return view();
    }

    using const_view_t = tensor_view<const T, NDIMS>;
    const_view_t view() const {
        return tensor_view<const T, NDIMS>(shape, strides, data);
    }
    operator const_view_t() const {
        return view();
    }

    T& operator[] (std::array<int, NDIMS> idx) { return view()[idx]; }
    T& at(std::array<int, NDIMS> idx) { return view().at(idx); }
    const T& operator[] (std::array<int, NDIMS> idx) const { return view()[idx]; }
    const T& at(std::array<int, NDIMS> idx) const { return view().at(idx); }

    template <int D = NDIMS>
    typename std::enable_if<(0 < D), tensor_view<T, NDIMS-1>>::type operator[] (int idx) {
        return view()[idx];
    }
    template <int D =NDIMS>
    typename std::enable_if<(0 < D), tensor_view<T, NDIMS-1>>::type at(int idx) {
        return view().at(idx);
    }

    template <int D = NDIMS>
    typename std::enable_if<(0 < D), tensor_view<const T, NDIMS-1>>::type operator[] (int idx) const {
        return view()[idx];
    }
    template <int D = NDIMS>
    typename std::enable_if<(0 < D), tensor_view<const T, NDIMS-1>>::type at(int idx) const {
        return view().at(idx);
    }

    template <int D = NDIMS>
    typename std::enable_if<(0 == D), T&>::type operator * () {
        return *view();
    }
    template <int D = NDIMS>
    typename std::enable_if<(0 == D), const T&>::type operator * () const {
        return *view();
    }
};

int main() {
    using namespace std;
    ios_base::sync_with_stdio(false), cin.tie(nullptr);

    int T; cin >> T;
    for (int case_num = 1; case_num <= T; case_num ++) {

        int N; cin >> N;
        tensor<int, 2> A({N, N});
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                cin >> A[{i,j}];
            }
        }
        tensor<int, 2> B({N, N});
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                cin >> B[{i,j}];
            }
        }
        vector<int> R(N);
        for (auto& r : R) cin >> r;
        vector<int> C(N);
        for (auto& c : C) cin >> c;

        vector<vector<array<int, 2>>> vals(1001);
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                vals[B[{i,j}]].push_back({i,j});
            }
        }

        const int V = 2 * N;
        vector<int> par(V, -1);
        auto get_par = [&](int a) -> int {
            while (par[a] >= 0) {
                if (par[par[a]] >= 0) par[a] = par[par[a]];
                a = par[a];
            }
            return a;
        };
        auto merge = [&](int a, int b) -> bool {
            a = get_par(a);
            b = get_par(b);
            if (a == b) return false;
            if (par[a] > par[b]) swap(a, b);
            par[a] += par[b];
            par[b] = a;
            return true;
        };

        int64_t ans = 0;
        for (int v = 1000; v >= 0; v--) {
            for (auto [i, j] : vals[v]) {
                if (!merge(i,N+j)) ans += v;
            }
        }

        cout << "Case #" << case_num << ": " << ans << '\n';
    }

    return 0;
}