結果

問題 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;
}
0