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

• 問題: No.3724 Domination
• ユーザー: 👑 kencho
• 提出日時: 2026-06-30 16:04:58
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 121 ms / 2,000 ms
• コード長: 5,131 bytes
• コンパイル時間: 2,554 ms
• コンパイル使用メモリ: 354,412 KB
• 実行使用メモリ: 35,584 KB
• 最終ジャッジ日時: 2026-09-19 12:31:03
• 合計ジャッジ時間: 17,980 ms
• ジャッジサーバーID （参考情報）: judge1_1 / judge2_0

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

ソースコード

#include <bits/stdc++.h>
using namespace std;

struct Dinic {
    struct Edge {
        int to;
        int rev;
        int cap;
    };

    vector<vector<Edge>> graph;
    vector<int> level;
    vector<int> iteratorIndex;

    explicit Dinic(int n) : graph(n), level(n), iteratorIndex(n) {}

    int addEdge(int from, int to, int cap) {
        Edge forward{to, static_cast<int>(graph[to].size()), cap};
        Edge backward{from, static_cast<int>(graph[from].size()), 0};
        graph[from].push_back(forward);
        graph[to].push_back(backward);
        return static_cast<int>(graph[from].size()) - 1;
    }

    bool bfs(int source, int sink) {
        fill(level.begin(), level.end(), -1);
        queue<int> q;
        level[source] = 0;
        q.push(source);
        while (!q.empty()) {
            int vertex = q.front();
            q.pop();
            for (const Edge& edge : graph[vertex]) {
                if (edge.cap > 0 && level[edge.to] < 0) {
                    level[edge.to] = level[vertex] + 1;
                    q.push(edge.to);
                }
            }
        }
        return level[sink] >= 0;
    }

    int dfs(int vertex, int sink, int flow) {
        if (vertex == sink) {
            return flow;
        }
        for (int& i = iteratorIndex[vertex]; i < static_cast<int>(graph[vertex].size()); i++) {
            Edge& edge = graph[vertex][i];
            if (edge.cap <= 0 || level[vertex] >= level[edge.to]) {
                continue;
            }
            int pushed = dfs(edge.to, sink, min(flow, edge.cap));
            if (pushed == 0) {
                continue;
            }
            edge.cap -= pushed;
            graph[edge.to][edge.rev].cap += pushed;
            return pushed;
        }
        return 0;
    }

    int maxFlow(int source, int sink) {
        int result = 0;
        while (bfs(source, sink)) {
            fill(iteratorIndex.begin(), iteratorIndex.end(), 0);
            while (true) {
                int pushed = dfs(source, sink, 1'000'000'000);
                if (pushed == 0) {
                    break;
                }
                result += pushed;
            }
        }
        return result;
    }
};

bool solveCase(int n, const vector<int>& r, const vector<int>& c, vector<vector<int>>& answer) {
    if (n == 1) {
        answer.assign(1, vector<int>(1, 1));
        return true;
    }
    if (n == 2) {
        return false;
    }

    vector<int> rowOfValue(n + 1);
    for (int row = 0; row < n; row++) {
        rowOfValue[r[row]] = row;
    }

    vector<vector<int>> columnsOfValue(n + 1);
    for (int col = 0; col < n; col++) {
        columnsOfValue[c[col]].push_back(col);
    }

    int rowCapacity = (n - 1) / 2;
    int source = 0;
    int labelBase = 1;
    int rowBase = labelBase + n;
    int sink = rowBase + n;
    Dinic dinic(sink + 1);
    vector<vector<int>> edgeIndex(n + 1, vector<int>(n + 1, -1));

    for (int value = 1; value <= n; value++) {
        dinic.addEdge(source, labelBase + value - 1, static_cast<int>(columnsOfValue[value].size()));
        for (int rowValue = 1; rowValue <= n; rowValue++) {
            if (rowValue == value) {
                continue;
            }
            edgeIndex[value][rowValue] = dinic.addEdge(labelBase + value - 1, rowBase + rowValue - 1, n);
        }
    }
    for (int rowValue = 1; rowValue <= n; rowValue++) {
        dinic.addEdge(rowBase + rowValue - 1, sink, rowCapacity);
    }

    if (dinic.maxFlow(source, sink) != n) {
        return false;
    }

    answer.assign(n, vector<int>(n));
    for (int row = 0; row < n; row++) {
        fill(answer[row].begin(), answer[row].end(), r[row]);
    }

    vector<int> pointer(n + 1, 0);
    for (int value = 1; value <= n; value++) {
        int labelNode = labelBase + value - 1;
        for (int rowValue = 1; rowValue <= n; rowValue++) {
            int index = edgeIndex[value][rowValue];
            if (index < 0) {
                continue;
            }
            const auto& edge = dinic.graph[labelNode][index];
            int used = dinic.graph[edge.to][edge.rev].cap;
            int row = rowOfValue[rowValue];
            for (int i = 0; i < used; i++) {
                int col = columnsOfValue[value][pointer[value]++];
                answer[row][col] = value;
            }
        }
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> r(n), c(n);
        for (int i = 0; i < n; i++) {
            cin >> r[i];
        }
        for (int i = 0; i < n; i++) {
            cin >> c[i];
        }

        vector<vector<int>> answer;
        if (!solveCase(n, r, c, answer)) {
            cout << -1 << '\n';
            continue;
        }

        for (int row = 0; row < n; row++) {
            for (int col = 0; col < n; col++) {
                if (col > 0) {
                    cout << ' ';
                }
                cout << answer[row][col];
            }
            cout << '\n';
        }
    }

    return 0;
}