結果

問題 No.3558 Dominoes, Black and White
コンテスト
ユーザー 土川智之
提出日時 2026-05-29 19:59:13
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
MLE  
実行時間 -
コード長 1,259 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 6,991 ms
コンパイル使用メモリ 360,048 KB
実行使用メモリ 1,307,244 KB
最終ジャッジ日時 2026-05-29 20:00:04
合計ジャッジ時間 16,544 ms
ジャッジサーバーID
（参考情報） 		judge1_1 / judge2_0
このコードへのチャレンジ
（要ログイン）
サブタスク 配点 結果
部分点 10 % AC * 30
満点 90 % AC * 30 MLE * 2 -- * 57
合計 10 点
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
#include <atcoder/mincostflow>

using namespace std;
using namespace atcoder;

using ll = long long;

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

    int N;
    cin >> N;

    vector<string> S(N);

    for (int i = 0; i < N; i++) {
        cin >> S[i];
    }

    vector<pair<int,int>> W, T;

    // 白マス
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < 2 * N; j++) {
            if (S[i][j] == '.') {
                W.push_back({i, j});
            }
        }
    }

    // 目標マス（左半分）
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            T.push_back({i, j});
        }
    }

    int K = N * N;

    int s = 2 * K;
    int t = 2 * K + 1;

    mcf_graph<int, ll> g(2 * K + 2);

    for (int i = 0; i < K; i++) {
        g.add_edge(s, i, 1, 0);
    }

    for (int j = 0; j < K; j++) {
        g.add_edge(K + j, t, 1, 0);
    }

    for (int i = 0; i < K; i++) {
        auto [r1, c1] = W[i];

        for (int j = 0; j < K; j++) {
            auto [r2, c2] = T[j];

            ll cost = abs(r1 - r2) + abs(c1 - c2);

            g.add_edge(i, K + j, 1, cost);
        }
    }

    auto ans = g.flow(s, t);

    cout << ans.second << '\n';
}
0