結果

問題 No.421 しろくろチョコレート
ユーザー anta
提出日時 2016-09-09 22:31:50
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 2,260 bytes
コンパイル時間 1,852 ms
コンパイル使用メモリ 177,884 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-09-23 07:04:37
合計ジャッジ時間 3,408 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 65
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include "bits/stdc++.h"
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
template<typename T, typename U> static void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> static void amax(T &x, U y) { if(x < y) x = y; }
#define aut(r,v) auto r = (v)
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
int bipartiteMatching(const vector<vector<int> > &g) {
    int nleft = g.size(), nright = 0;
    each(es, g) if(!es->empty()) nright = max(nright, *max_element(es->begin(), es->end()) + 1);
    vi matchL(nleft, -1), matchR(nright, -1), prev(nleft), seen(nleft, -1);
    rep(i, nleft) {
        vi stk; stk.push_back(i);
        seen[i] = i; prev[i] = -1;
        while(!stk.empty()) {
            int v = stk.back(); stk.pop_back();
            each(ui, g[v]) {
                int u = *ui;
                int j = matchR[u];
                if(j == -1) {
                    while(v != -1) {
                        matchR[u] = v;
                        swap(u, matchL[v]);
                        v = prev[v];
                    }
                    goto break_;
                } else if(seen[j] < i) {
                    seen[j] = i; prev[j] = v;
                    stk.push_back(j);
                }
            }
        }
    break_:;
    }
    return (int)matchL.size() - count(matchL.begin(), matchL.end(), -1);
}
int main() {
    int N; int M;
    while(~scanf("%d%d", &N, &M)) {
        vector<string> S(N);
        rep(i, N) {
            char buf[51];
            scanf("%s", buf);
            S[i] = buf;
        }
        vector<vi> g(N * M);
        rep(i, N) rep(j, M) if((i + j) % 2 == 0 && S[i][j] != '.') {
            static const int dy[4] = { 0, 1, 0, -1 }, dx[4] = { 1, 0, -1, 0 };
            for(int d = 0; d < 4; ++ d) {
                int yy = i + dy[d], xx = j + dx[d];
                if(yy < 0 || yy >= N || xx < 0 || xx >= M) continue;
                if(S[yy][xx] == '.') continue;
                g[i * M + j].push_back(yy * M + xx);
            }
        }
        int cnt[2] = {};
        rep(i, N) rep(j, M) if(S[i][j] != '.')
            ++ cnt[(i + j) % 2];
        int match = bipartiteMatching(g);
        int x = min(cnt[0], cnt[1]) - match;
        int y = cnt[0] + cnt[1] - match * 2 - x * 2;
        int ans = match * 100 + x * 10 + y;
        printf("%d\n", ans);
    }
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0