#1188204 (C++23) No.3724 Domination

• 問題: No.3724 Domination
• ユーザー: Rice_tawara459
• 提出日時: 2026-09-19 13:38:14
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 126 ms / 2,000 ms
• コード長: 7,662 bytes
• コンパイル時間: 2,504 ms
• コンパイル使用メモリ: 361,780 KB
• 実行使用メモリ: 82,376 KB
• 最終ジャッジ日時: 2026-09-19 13:38:32
• 合計ジャッジ時間: 16,525 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge2_0

サブタスク	配点	結果
部分点	20 %	AC * 8
満点	80 %	AC * 52
合計	2.5 * 100% = 250 点

ソースコード

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;

#define rep(i,n) for(ll i=0;i<n;++i)
#define all(a) (a).begin(),(a).end()
ll intpow(ll a, ll b){ ll ans = 1; while(b){ if(b & 1) ans *= a; a *= a; b /= 2; } return ans; }
ll modpow(ll a, ll b, ll p){ ll ans = 1; while(b){ if(b & 1) (ans *= a) %= p; (a *= a) %= p; b /= 2; } return ans; }
template<class T> T div_floor(T a, T b) { return a / b - ((a ^ b) < 0 && a % b); }
template<class T> T div_ceil(T a, T b) { return a / b + ((a ^ b) > 0 && a % b); }
template <typename T, typename U> inline bool chmin(T &x, U y) { return (y < x) ? (x = y, true) : false; }
template <typename T, typename U> inline bool chmax(T &x, U y) { return (x < y) ? (x = y, true) : false; }

template<typename T,typename U>
ostream &operator<<(ostream &os,const pair<T,U> &p){
    return os<<p.first<<' '<<p.second;
}

template<typename T>
ostream &operator<<(ostream &os, const vector<T> &a){
    if (a.empty()) return os;
    os << a.front();
    for (auto e : a | views::drop(1)){
        os << ' ' << e;
    }
    return os;
}

void dump(auto ...vs){
    ((cout << vs << ' '), ...) << endl;
}

#ifndef LIBRARY_GRAPH_MAXFLOW_HPP
#define LIBRARY_GRAPH_MAXFLOW_HPP

#line 1 "src/graph/maxflow.hpp"


#include <vector>
#include <queue>
#include <algorithm>
#include <cassert>
#include <limits>

template <class Cap>
struct mf_graph {
  public:
    mf_graph() : _n(0) {}
    explicit mf_graph(int n) : _n(n), g(n) {}

    /// from から to へ容量 cap の有向辺を追加し、辺番号を返す。
    int add_edge(int from, int to, Cap cap) {
        assert(0 <= from && from < _n);
        assert(0 <= to && to < _n);
        assert(0 <= cap);
        int m = int(pos.size());
        pos.push_back({from, int(g[from].size())});
        int from_id = int(g[from].size());
        int to_id = int(g[to].size());
        if (from == to) to_id++;
        g[from].push_back(_edge{to, to_id, cap});
        g[to].push_back(_edge{from, from_id, 0});
        return m;
    }

    struct edge {
        int from;
        int to;
        Cap cap;
        Cap flow;
    };

    /// i 番目に追加した辺の現在の容量・流量を返す。
    edge get_edge(int i) const {
        int m = int(pos.size());
        assert(0 <= i && i < m);
        auto _e = g[pos[i].first][pos[i].second];
        auto _re = g[_e.to][_e.rev];
        return edge{pos[i].first, _e.to, _e.cap + _re.cap, _re.cap};
    }

    /// 追加した全ての辺の現在状態を返す。
    std::vector<edge> edges() const {
        int m = int(pos.size());
        std::vector<edge> result;
        for (int i = 0; i < m; i++) {
            result.push_back(get_edge(i));
        }
        return result;
    }

    /// i 番目の辺の容量と流量を直接変更する。
    void change_edge(int i, Cap new_cap, Cap new_flow) {
        int m = int(pos.size());
        assert(0 <= i && i < m);
        assert(0 <= new_flow && new_flow <= new_cap);
        auto& _e = g[pos[i].first][pos[i].second];
        auto& _re = g[_e.to][_e.rev];
        _e.cap = new_cap - new_flow;
        _re.cap = new_flow;
    }

    /// s から t への最大流を流せるだけ流す。
    Cap flow(int s, int t) {
        return flow(s, t, std::numeric_limits<Cap>::max());
    }
    /// 流量上限 flow_limit まで、s から t への最大流を流す。
    Cap flow(int s, int t, Cap flow_limit) {
        assert(0 <= s && s < _n);
        assert(0 <= t && t < _n);
        assert(s != t);

        std::vector<int> level(_n), iter(_n);
        
        auto bfs = [&]() {
            std::fill(level.begin(), level.end(), -1);
            level[s] = 0;
            std::queue<int> que;
            que.push(s);
            while (!que.empty()) {
                int v = que.front();
                que.pop();
                for (const auto& e : g[v]) {
                    if (e.cap == 0 || level[e.to] >= 0) continue;
                    level[e.to] = level[v] + 1;
                    if (e.to == t) return;
                    que.push(e.to);
                }
            }
        };

        auto dfs = [&](auto self, int v, Cap up) -> Cap {
            if (v == s) return up;
            Cap res = 0;
            int level_v = level[v];
            for (int& i = iter[v]; i < int(g[v].size()); i++) {
                _edge& e = g[v][i];
                if (level_v <= level[e.to] || g[e.to][e.rev].cap == 0) continue;
                Cap d = self(self, e.to, std::min(up - res, g[e.to][e.rev].cap));
                if (d <= 0) continue;
                g[e.to][e.rev].cap -= d;
                g[v][i].cap += d;
                res += d;
                if (res == up) return res;
            }
            level[v] = _n;
            return res;
        };

        Cap flow = 0;
        while (flow < flow_limit) {
            bfs();
            if (level[t] == -1) break;
            std::fill(iter.begin(), iter.end(), 0);
            while (flow < flow_limit) {
                Cap f = dfs(dfs, t, flow_limit - flow);
                if (!f) break;
                flow += f;
            }
        }
        return flow;
    }

    /// 最後の flow 後の残余グラフで、s から到達可能な頂点集合を返す。
    std::vector<bool> min_cut(int s) {
        std::vector<bool> visited(_n, false);
        std::queue<int> que;
        que.push(s);
        visited[s] = true;
        while (!que.empty()) {
            int p = que.front();
            que.pop();
            for (const auto& e : g[p]) {
                if (e.cap > 0 && !visited[e.to]) {
                    visited[e.to] = true;
                    que.push(e.to);
                }
            }
        }
        return visited;
    }

  private:
    int _n;
    struct _edge {
        int to;
        int rev;
        Cap cap;
    };
    std::pair<int, int> pos_t;
    std::vector<std::pair<int, int>> pos;
    std::vector<std::vector<_edge>> g;
};

#endif  // LIBRARY_GRAPH_MAXFLOW_HPP


void solve() {
    ll N;
    cin>>N;
    vector<ll> R(N),C(N);
    rep(i,N)cin>>R[i];
    rep(i,N)R[i]--;
    rep(i,N)cin>>C[i];
    rep(i,N)C[i]--;
    if (N==1){
        cout<<1<<'\n';
        return;
    }
    if (N==2){
        cout<<-1<<'\n';
        return;
    }
    assert(N>=3);
    vector<ll> IR(N);
    rep(i,N){
        IR[R[i]]=i;
    }
    rep(i,N){
        C[i]=IR[C[i]];
    }
    vector A(N,vector<ll> (N));
    rep(i,N){
        rep(j,N){
            A[i][j]=i;
        }
    }
    if (*max_element(all(C))==*min_element(all(C))){
        if (N<=4){
            cout<<-1<<'\n';
            return;
        }
        rep(j,N){
            if (j==C[j]){
                A[(j+1)%N][j]=C[j];
            }
            else{
                A[j][j]=C[j];
            }
        }
    }
    else{
        ll src=2*N;
        ll tar=src+1;
        mf_graph<ll> mf(tar+1);
        rep(j,N){
            rep(i,N){
                if (C[j]!=i)mf.add_edge(j,N+i,1);
            }
            mf.add_edge(src,j,1);
            mf.add_edge(N+j,tar,1);
        }
        mf.flow(src,tar);
        for (auto e:mf.edges()){
            if (e.from==src)continue;
            if (e.to==tar)continue;
            if (e.flow>0){
                A[e.to-N][e.from]=C[e.from];
            }
        }
    }
    rep(i,N){
        rep(j,N){
            A[i][j]=R[A[i][j]];
            A[i][j]++;
        }
    }
    rep(i,N){
        cout<<A[i]<<'\n';
    }
    return;
}


int main() {
    cin.tie(0)->sync_with_stdio(0);
    ll T=1;
    cin>>T;
    while (T--){
        solve();
    }
    return 0;
}