結果

問題 No.348 カゴメカゴメ
コンテスト
ユーザー koyumeishi
提出日時 2016-02-27 00:37:00
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 4,529 bytes
コンパイル時間 1,695 ms
コンパイル使用メモリ 133,820 KB
実行使用メモリ 60,884 KB
最終ジャッジ日時 2024-09-24 10:48:05
合計ジャッジ時間 6,824 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 47 WA * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <cstdio>
#include <sstream>
#include <map>
#include <string>
#include <algorithm>
#include <queue>
#include <cmath>
#include <functional>
#include <set>
#include <ctime>
#include <random>
using namespace std;
template<typename T> istream& operator >> (istream& is, vector<T>& vec){for(T& val: vec) is >> val; return is;}
template<typename T> istream& operator , (istream& is, T& val){ return is >> val;}
template<typename T> ostream& operator << (ostream& os, const vector<T>& vec){for(int i=0; i<vec.size(); i++) os << vec[i] << (i==vec.size()-1?"\n":" ");return os;}
template<typename T> ostream& operator , (ostream& os, T& val){ return os << " " << val;}
template<typename T> ostream& operator >> (ostream& os, T& val){ return os << " " << val;}

using namespace std;

class UnionFindTree{
	struct base_node{
		int parent;
		int rank;
		int size;
	};
	
	vector<base_node> node;
public:
	UnionFindTree(int n){
		node.resize(n);
		for(int i=0; i<n; i++){
			node[i].parent=i;
			node[i].rank=0;
			node[i].size=1;
		}
	}

	int find(int x){  //return root node of x
		if(node[x].parent == x) return x;
		else{
			return node[x].parent = find(node[x].parent);
		}
	}
	
	bool same(int x, int y){
		return find(x) == find(y);
	}

	int size(int at){
		return node[find(at)].size;
	}

	void unite(int x, int y){
		x = find(node[x].parent);
		y = find(node[y].parent);

		if(x==y) return;

		if(node[x].rank < node[y].rank){
			node[x].parent = y;
			node[y].size += node[x].size;
		}else if(node[x].rank > node[y].rank){
			node[y].parent = x;
			node[x].size += node[y].size;
		}else{
			node[x].rank++;
			unite(x,y);
		}
	}
};

int dx[] = {0,0,1,-1,1,-1,1,-1};
int dy[] = {1,-1,0,0,1,1,-1,-1};

int main(){
	int n,m;
	cin >> n,m;
	vector<string> v(n+2, string(m+2, '.'));
	for(int i=1; i<=n; i++){
		string tmp;
		cin >> tmp;
		v[i] = '.' + tmp + '.';
	}
	n+=2;
	m+=2;

	UnionFindTree uft(n*m);

	for(int i=0; i<n; i++) for(int j=0; j<m; j++){
		if(v[i][j] == 'x') for(int k=0; k<8; k++){
			int ii = i+dy[k];
			int jj = j+dx[k];
			if(ii < 0 || ii>=n) continue;
			if(jj < 0 || jj>=m) continue;
			if(v[ii][jj] == 'x') uft.unite(i*m+j, ii*m+jj);
		}
	}

	int t=0;
	set<int> s;
	for(int i=0;i<n;i++)for(int j=0;j<m;j++)if(v[i][j]=='x')s.insert(uft.find(i*m+j)); t=s.size(); 
	//cerr << t << endl;

	map<int, set<int>> G;
	queue<int> q;
	vector<bool> visit( n*m , false);
	set<int> next;

	vector<vector<int>> w(n, vector<int>(m, -1));
	{//round
		q.push(0);
		visit[0] = true;
		while(q.size()){
			auto pos = q.front(); q.pop();
			int r = pos/m;
			int c = pos%m;
			w[r][c] = 0;
			for(int k=0; k<4; k++){
				int rr = r+dy[k];
				int cc = c+dx[k];
				if(rr < 0 || rr>=n) continue;
				if(cc < 0 || cc>=m) continue;
				if(visit[rr*m + cc]) continue;
				if(v[rr][cc] == 'x'){
					next.insert(uft.find(rr*m + cc));
					continue;
				}
				visit[rr*m + cc] = true;
				q.push(rr*m + cc);
			}
		}
		for(int unko : next){ q.push(unko); G[0].insert(unko); }
	}


	while(q.size()){
		auto p = q.front();
		q.pop();
		int r = p/m;
		int c = p%m;

		int val = uft.find(p);
		set<int> tmp;
		{
			function<void(int,int)> dfs0 = [&](int r, int c){
				w[r][c] = val;
				for(int k=0; k<8; k++){
					int rr = r+dy[k];
					int cc = c+dx[k];
					if(rr < 0 || rr>=n) continue;
					if(cc < 0 || cc>=m) continue;
					if(w[rr][cc] != -1) continue;
					if(v[rr][cc] == '.'){
						tmp.insert(uft.find(rr*m + cc));
						continue;
					}
					dfs0(rr,cc);
				}
			};
			dfs0(r,c);
		}

		set<int> next;
		function<void(int,int)> dfs = [&](int r, int c){
			if(visit[r*m+c]) return;
			if(v[r][c] == 'x'){
				next.insert(r*m + c);
				return;
			}
			w[r][c] = val;
			visit[r*m+c] = true;

			for(int k=0; k<4; k++){
				int rr = r+dy[k];
				int cc = c+dx[k];
				if(rr < 0 || rr>=n) continue;
				if(cc < 0 || cc>=m) continue;
				if(w[rr][cc] != -1) continue;
				dfs(rr,cc);
			}
		};
		for(int hoge : tmp) dfs(hoge/m, hoge%m);

		for(int ch : next){
			G[p].insert(uft.find(ch));
			q.push(ch);
		}
	}

	vector<map<int,long long>> memo(2);

	long long ans = 0;
	function<long long(int,int)> dfs = [&](int pos, int use){
		if(memo[use].find(pos) != memo[use].end()) return memo[use][pos];
		long long ret = 0;
		if(pos != 0 && use) ret += uft.size(pos);
		for(auto ch : G[pos]){
			if(use) ret += dfs(ch, 0);
			else ret += max(dfs(ch, 0), dfs(ch, 1));
		}
		if(pos != 0) memo[use][pos] = ret;
		return ret;
	};

	ans = max(dfs(0,0), dfs(0,1));
	cout << ans << endl;
	return 0;
}
0