結果

問題 No.348 カゴメカゴメ
ユーザー 37zigen37zigen
提出日時 2016-06-14 18:21:44
言語 C++11
(gcc 11.4.0)
結果
RE  
実行時間 -
コード長 2,745 bytes
コンパイル時間 1,104 ms
コンパイル使用メモリ 75,956 KB
実行使用メモリ 814,940 KB
最終ジャッジ日時 2024-04-17 19:31:39
合計ジャッジ時間 4,648 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 RE -
testcase_01 RE -
testcase_02 RE -
testcase_03 RE -
testcase_04 RE -
testcase_05 MLE -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
testcase_38 -- -
testcase_39 -- -
testcase_40 -- -
testcase_41 -- -
testcase_42 -- -
testcase_43 -- -
testcase_44 -- -
testcase_45 -- -
testcase_46 -- -
testcase_47 -- -
testcase_48 -- -
testcase_49 -- -
testcase_50 -- -
testcase_51 -- -
testcase_52 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <vector>
#include <utility>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
struct DJSet{
	vector<int> data;
	void init(int n){
		data.assign(n, -1);
	}
	bool unionSet(int x, int 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;
		}
		return x != y;
	}
	bool findSet(int x, int y){
		return root(x) == root(y);
	}
	int root(int x){
		return data[x]<0 ? x : root(data[x]);
	}
	int size(int x){
		return -data[root(x)];
	}
};
vector<int> memo;
int rec(int i, int p, bool b, const vector<vector<int>> &g, const vector<string>grid, DJSet &ds){
	int &r = memo[i * 2 + b];
	if (r == -2)cerr << "error" << endl;
	if (r != -1)return r;
	if (grid[i / grid[0].size()][i%grid[0].size()] == '.'){
		int t = 0;
		for (int j = 0; j < g[i].size(); j++){
			if (g[i][j] != p){
				t += rec(g[i][j], i, b,g, grid, ds);
			}
		}
		r = t;
	}
	else{
		int t = 0, u = 0;
		for (int j = 0; j < g[i].size(); j++){
			int to = g[i][j];
			if (to != p)
			{
				int x = rec(to, i, false, g, grid, ds);
				int y = rec(to, i, true, g, grid, ds);
				t += max(x, y);
				u += y;
			}
		}
		r = t;
		if (!b){
			r = max(r, u + ds.size(i));
		}
	}
	
	return r;
}
int main(){
	int N, M;
	while (~scanf("%d%d", &N, &M)){
		vector<string> grid(N + 2);
		grid[0] = string(M, '.'); 
		for (int i = 0; i < M; i++){
			cin >> grid[i+1];
		}
		for (int i = 0; i < N + 2; i++){
			grid[i] = "." + grid[i] + ".";
		}
		N += 2;
		M += 2;
		DJSet ds;
		ds.init(N*M);
		for (int i = 0; i < N; i++){
			for (int j = 0; j < M; j++){
				for (int dx = -1; dx <= 1; dx++){
					for (int dy = -1; dy <= 1; dy++){
						if (dx || dy){
							int yy = i + dy;
							int xx = j + dx;
							if (yy == -1 || xx == -1 || yy == N || xx == M)continue;
							if (grid[i][j] = '.'&&abs(dx) + abs(dy) > 1)continue;
							if (grid[i][j] != grid[yy][xx])continue;
							ds.unionSet(i*M + j, yy*M+xx);

						}
					}
				}
			}
		}
		vector<vector<int>> g(N*M);
		for (int i = 0; i < N; i++){
			for (int j = 0; j < M; j++){
				for (int dx = -1; dx <= 1; dx++){
					for (int dy = -1; dy <= 1; dy++){
						if (dx || dy){
							int yy = i + dy;
							int xx = j + dx;
							if (yy == -1 || xx == -1 || yy == N || xx == M)continue;
							if (abs(dx) + abs(dy) > 1)continue;
							if (grid[i][j] != grid[yy][xx]){
								g[ds.root(i*M + j)].push_back(ds.root(yy*M + j));
							}
						}
					}
				}
			}
		}
		for (int i = 0; i < N*M; i++){
			vector<int> &v = g[i];
			sort(v.begin(), v.end());
			v.erase(unique(v.begin(), v.end()), v.end());
		}
		memo.assign(N*M * 2, -1);
		int ans=rec(ds.root(N*M-1),-1,false,g,grid,ds);
		printf("%d\n", ans);
		
	}
	return 0;
}
0