結果

問題 No.421 しろくろチョコレート
コンテスト
ユーザー FF256grhy
提出日時 2016-09-10 00:22:23
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 3,017 bytes
コンパイル時間 369 ms
コンパイル使用メモリ 27,616 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-16 19:05:08
合計ジャッジ時間 1,873 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 32 WA * 33
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:112:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  112 |         scanf("%d%d", &n, &m);
      |         ~~~~~^~~~~~~~~~~~~~~~
main.cpp:113:26: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  113 |         INC(i, n) { scanf("%s", s[i]); }
      |                     ~~~~~^~~~~~~~~~~~

ソースコード

diff # 

#include <cstdio>

#define FOR( i, l, r) for(int i = (l)    ; i <  (r); i++)
#define FOR1(i, l, r) for(int i = (l)    ; i <= (r); i++)
#define REV( i, l, r) for(int i = (r) - 1; i >= (l); i--)
#define REV1(i, l, r) for(int i = (r)    ; i >= (l); i--)
#define INC( i, n) FOR( i, 0, n)
#define INC1(i, n) FOR1(i, 1, n)
#define DEC( i, n) REV( i, 0, n)
#define DEC1(i, n) REV1(i, 1, n)

typedef long long   signed int LL;
typedef long long unsigned int LU;

// ---- ----

template<typename T> T max(T a, T b) { return (a > b ? a : b); }
template<typename T> T min(T a, T b) { return (a < b ? a : b); }
template<typename T> T abs(T x) { return (x > 0 ? x : -x); }


int n, m;
char s[50][51];

class UnionFind {
public:
	UnionFind(int size);
	int unite(int v, int w);
	int find(int v);
	int get_size_eq(int v);
	int get_size_part();
	virtual ~UnionFind();
	
	int get_black(int v);
	int get_white(int v);

private:
	int *parent;
	int *size_eq;
	int size_part;
	
	int *black;
	int *white;
};

UnionFind::UnionFind(int size) {
	parent = new int[size];
	size_eq = new int[size];
	black = new int[size];
	white = new int[size];
	for(int i = 0; i < size; i++) { parent[i] = -1; size_eq[i] = 1; black[i] = (s[i / m][i % m] == 'b'); white[i] = (s[i / m][i % m] == 'w'); }
	size_part = size;
}

int UnionFind::unite(int v, int w) {
	int fv = find(v);
	int fw = find(w);
	if(fv == fw) { return fv; }
	
	size_part--;
	int &sv = size_eq[fv];
	int &sw = size_eq[fw];
	
	if(sv < sw) {
		parent[fv] = fw;
		sw += sv;
		black[fw] += black[fv];
		white[fw] += white[fv];
		return fw;
	} else {
		parent[fw] = fv;
		sv += sw;
		black[fv] += black[fw];
		white[fv] += white[fw];
		return fv;
	}
}

int UnionFind::find(int v) {
	if(parent[v] == -1) { return v; }
	return parent[v] = find( parent[v] );
}

int UnionFind::get_size_eq(int v) {
	return size_eq[ find(v) ];
}

int UnionFind::get_size_part() {
	return size_part;
}

UnionFind::~UnionFind() {
	delete[] parent;
	delete[] size_eq;
	
	delete[] black;
	delete[] white;
}

int UnionFind::get_black(int v) {
	return black[ find(v) ];
}
int UnionFind::get_white(int v) {
	return white[ find(v) ];
}



int memo[50 * 50], cnt_w, cnt_b, ans;

int main() {
	scanf("%d%d", &n, &m);
	INC(i, n) { scanf("%s", s[i]); }
	
	UnionFind uf(n * m);
	
	INC(i, n) {
	INC(j, m) {
		if(s[i][j] != '.') {
			if(i + 1 < n && s[i + 1][j] != '.') { uf.unite(i * m + j, (i + 1) * m + j); }
			if(j + 1 < m && s[i][j + 1] != '.') { uf.unite(i * m + j, i * m + (j + 1)); }
		}
	}
	}
	
	INC(i, n) {
	INC(j, m) {
		if(s[i][j] == 'w') { cnt_w++; }
		if(s[i][j] == 'b') { cnt_b++; }
	}
	}
	
	INC(i, n) {
	INC(j, m) {
		int v = i * m + j;
		int fv = uf.find(v);
		if(memo[fv] == 0) {
			memo[fv] = 1;
			int b = uf.get_black(v);
			int w = uf.get_white(v);
			
			//printf("i: %d, j: %d, fv: %d, b:%d, w: %d\n", i, j, fv, b, w);
			
			ans += min(b, w) * 100;
			cnt_w -= min(b, w);
			cnt_b -= min(b, w);
		}
	}
	}
	
	ans += min(cnt_w, cnt_b) * 10;
	ans += abs(cnt_w - cnt_b);
	
	printf("%d\n", ans);
	
	return 0;
}
0