#78640 (C++11) No.348 カゴメカゴメ

提出ソース

結果

問題	No.348 カゴメカゴメ
ユーザー	koyumeishi
提出日時	2016-02-27 00:44:26
言語	C++11 (gcc 11.4.0)
結果	AC
実行時間	501 ms / 2,000 ms
コード長	4,564 bytes
コンパイル時間	1,614 ms
コンパイル使用メモリ	134,476 KB
実行使用メモリ	60,968 KB
最終ジャッジ日時	2024-09-24 10:49:35
合計ジャッジ時間	6,047 ms
ジャッジサーバーID （参考情報）	judge1 / judge5

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	131 ms 21,528 KB
testcase_01	AC	2 ms 6,940 KB
testcase_02	AC	501 ms 60,968 KB
testcase_03	AC	210 ms 21,860 KB
testcase_04	AC	2 ms 6,940 KB
testcase_05	AC	2 ms 6,940 KB
testcase_06	AC	1 ms 6,940 KB
testcase_07	AC	2 ms 6,944 KB
testcase_08	AC	2 ms 6,940 KB
testcase_09	AC	2 ms 6,944 KB
testcase_10	AC	2 ms 6,944 KB
testcase_11	AC	1 ms 6,940 KB
testcase_12	AC	4 ms 6,940 KB
testcase_13	AC	3 ms 6,940 KB
testcase_14	AC	2 ms 6,944 KB
testcase_15	AC	57 ms 21,104 KB
testcase_16	AC	2 ms 6,944 KB
testcase_17	AC	2 ms 6,944 KB
testcase_18	AC	2 ms 6,940 KB
testcase_19	AC	1 ms 6,940 KB
testcase_20	AC	2 ms 6,944 KB
testcase_21	AC	2 ms 6,940 KB
testcase_22	AC	2 ms 6,944 KB
testcase_23	AC	180 ms 24,752 KB
testcase_24	AC	174 ms 24,940 KB
testcase_25	AC	176 ms 24,464 KB
testcase_26	AC	179 ms 24,604 KB
testcase_27	AC	175 ms 25,220 KB
testcase_28	AC	180 ms 24,668 KB
testcase_29	AC	177 ms 24,720 KB
testcase_30	AC	176 ms 24,604 KB
testcase_31	AC	179 ms 24,804 KB
testcase_32	AC	179 ms 24,924 KB
testcase_33	AC	15 ms 6,940 KB
testcase_34	AC	14 ms 6,944 KB
testcase_35	AC	15 ms 6,944 KB
testcase_36	AC	14 ms 6,944 KB
testcase_37	AC	15 ms 6,940 KB
testcase_38	AC	15 ms 6,944 KB
testcase_39	AC	15 ms 6,940 KB
testcase_40	AC	14 ms 6,940 KB
testcase_41	AC	14 ms 6,940 KB
testcase_42	AC	15 ms 6,940 KB
testcase_43	AC	3 ms 6,944 KB
testcase_44	AC	3 ms 6,940 KB
testcase_45	AC	3 ms 6,940 KB
testcase_46	AC	4 ms 6,944 KB
testcase_47	AC	3 ms 6,944 KB
testcase_48	AC	4 ms 6,944 KB
testcase_49	AC	4 ms 6,944 KB
testcase_50	AC	4 ms 6,944 KB
testcase_51	AC	3 ms 6,940 KB
testcase_52	AC	3 ms 6,944 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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){
				visit[r*m+c] = true;
				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(uft.find(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;
}

yukicoder

結果

テストケース

ソースコード