結果

問題 No.421 しろくろチョコレート
ユーザー moyashi_senpai
提出日時 2016-09-09 23:37:33
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 2,881 bytes
コンパイル時間 1,036 ms
コンパイル使用メモリ 101,896 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-11-16 18:41:31
合計ジャッジ時間 2,575 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 22 WA * 43
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:76:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   76 |         scanf("%d %d", &h, &w);
      |         ~~~~~^~~~~~~~~~~~~~~~~
main.cpp:80:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   80 |                 scanf("%*c");
      |                 ~~~~~^~~~~~~
main.cpp:83:30: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   83 |                         scanf("%c", &c);
      |                         ~~~~~^~~~~~~~~~

ソースコード

diff # 

#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <cstring>
#include <numeric>
#include <algorithm>
#include <functional>
#include <array>
#include <map>
#include <queue>
#include <limits.h>
#include <set>
#include <stack>
#define REP(i,n) for(int i = 0; n > i; i++)
#define MOD 1000000007
using namespace std;
typedef vector<int> Ivec;
typedef pair<int, int> pii;
typedef long long int ll;
const pii four_Dir[4] = { //四方向
	{ 1 ,0 },{ 0 ,1 },{ 0,-1 },{ -1 ,0 }
};

struct UnionFind {
	vector<int> data;
	map<int, pii> roots;
	UnionFind(int size) : data(size, -1) { }
	bool unionSet(int x, int y) { //ｘの入ってる集合と yの入ってる集合を併合
		//int oriy = y;
		x = root(x); y = root(y);
		if (x != y) {
			if (data[y] < data[x]) swap(x, y);
			data[x] += data[y]; data[y] = x;
			if (roots[x].first == 0 && roots[x].second == 0) {
				if (x % 2)
					roots[x].second = 1;
				else roots[x].first = 1;
			}
			if (roots[y].first == 0 && roots[y].second == 0) {
				if (y % 2) //黒
					roots[x].second++;
				else roots[x].first++;
			}
			else {
				roots[x].first += roots[y].first;
				roots[x].second += roots[y].second;
			}
			roots.erase(y);
		}
		return x != y;
	}
	bool Isroot(int x) {
		return roots.find(x) != roots.end() ? true : false;
	}
	vector<pii> Getroots() {
		vector<pii> res;
		for (auto itr = roots.begin(); itr != roots.end(); itr++) {
			res.push_back(itr->second);
		}
		return res;
	}
	bool findSet(int x, int y) { //xとyが同じ集合に入っているかどうかを判定
		return root(x) == root(y);
	}
	int root(int x) {
		return data[x] < 0 ? x : data[x] = root(data[x]);
	}
	int size(int x) {
		return -data[root(x)];
	}
};

int main() {
	int w, h;
	scanf("%d %d", &h, &w);
	vector<vector<int>> choco(w+1,vector<int>(h+1,0));
	UnionFind uf(2500);
	REP(i, h) {
		scanf("%*c");
		REP(j, w) {
			char c;
			scanf("%c", &c);
			if (c == '.') choco[j][i] = 0;
			else if (c == 'w') choco[j][i] = 1;
			else choco[j][i] = 2;
		}
	}

	int w_ama = 0, b_ama = 0;
	REP(i, h) {
		REP(j, w) {
			if (choco[j][i]) {
				bool f = false;
				REP(k, 4) {
					pii next = { j + four_Dir[k].first, i + four_Dir[k].second };
					if (min(next.first, next.second) >= 0) {
						if (choco[next.first][next.second]) {
							uf.unionSet(i*w + j, next.second*w + next.first);
							f = true;
						}
					}
				}
				if (!f) {
					if ((i*w + j) % 2) {
						b_ama++;
					}
					else w_ama++;
				}
			}
		}
	}

	vector<pii> chocos = uf.Getroots();
	int happiness = 0;
	REP(i, chocos.size()) {
		pii num = chocos[i];
		happiness += min(num.first, num.second)*100;
		if (num.first > num.second) {
			w_ama += num.first - num.second;
		}
		else b_ama += num.second - num.first;
	}
	happiness += min(w_ama, b_ama) * 10;
	happiness += max(w_ama, b_ama) - min(w_ama, b_ama);
	printf("%d\n", happiness);
	return 0;
}
0