結果

問題 No.421 しろくろチョコレート
ユーザー moyashi_senpaimoyashi_senpai
提出日時 2016-09-09 23:37:33
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 2,881 bytes
コンパイル時間 996 ms
コンパイル使用メモリ 100,336 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-04-28 05:56:47
合計ジャッジ時間 2,668 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 AC 2 ms
6,944 KB
testcase_03 WA -
testcase_04 AC 2 ms
6,940 KB
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 AC 2 ms
6,940 KB
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 AC 2 ms
6,944 KB
testcase_13 AC 2 ms
6,940 KB
testcase_14 AC 1 ms
6,940 KB
testcase_15 AC 1 ms
6,944 KB
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 AC 1 ms
6,940 KB
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 AC 2 ms
6,940 KB
testcase_24 AC 1 ms
6,940 KB
testcase_25 AC 1 ms
6,940 KB
testcase_26 AC 2 ms
6,940 KB
testcase_27 AC 2 ms
6,944 KB
testcase_28 AC 2 ms
6,940 KB
testcase_29 WA -
testcase_30 WA -
testcase_31 AC 2 ms
6,944 KB
testcase_32 WA -
testcase_33 WA -
testcase_34 WA -
testcase_35 WA -
testcase_36 WA -
testcase_37 WA -
testcase_38 WA -
testcase_39 WA -
testcase_40 AC 2 ms
6,944 KB
testcase_41 WA -
testcase_42 WA -
testcase_43 WA -
testcase_44 WA -
testcase_45 WA -
testcase_46 WA -
testcase_47 WA -
testcase_48 AC 2 ms
6,940 KB
testcase_49 WA -
testcase_50 WA -
testcase_51 AC 2 ms
6,940 KB
testcase_52 WA -
testcase_53 WA -
testcase_54 AC 2 ms
6,940 KB
testcase_55 WA -
testcase_56 WA -
testcase_57 WA -
testcase_58 WA -
testcase_59 WA -
testcase_60 WA -
testcase_61 WA -
testcase_62 AC 2 ms
6,944 KB
testcase_63 AC 2 ms
6,940 KB
testcase_64 AC 2 ms
6,940 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
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