Submission #1419061


Source Code Expand

#include <bits/stdc++.h>
using namespace std;

#define for_(i,a,b) for(int i=(a);i<(b);++i)
#define for_rev(i,a,b) for(int i=(a);i>=(b);--i)
typedef unsigned int hash_type;
struct Edge { int u, v; };

const char NON = char(0);
const char IN = char(1);
const int MAXI = (int)1e9;

int H, W, num_tree, V, E;
vector< Edge > edges;
string c[10];

bool is_home[102], is_tree[102], is_null[102], sum_home[102];
int last_edge[100], px[100], py[100], deg[100];
unordered_map< hash_type, int > memo[200];

hash_type calcHash(string& mate) {
	hash_type res = 0;
	for_(i,0,W) res += (res << 3) | mate[i];
	return res;
}

char newBlock(string& mate) {
	char res = NON;
	for_(i,0,W+1) res = max(res, mate[i]);
	return char(res + 1);
}

void merge(string& mate, char a, char b) {
	for_(i,0,W+1) if (mate[i] == b) mate[i] = a;
	
	map< char, char > replace_id;
	char cur_id = IN;

	for_(i,0,W+1) {
		if (mate[i] >= IN) {
			char s = mate[i];
			if (replace_id.count(s)) mate[i] = replace_id[s];
			else mate[i] = replace_id[s] = cur_id, ++cur_id;
		}
	}
}

int checkout(string& mate, int v, int vx, int vy) {
	char s = mate[vx];
	mate[vx] = NON;
	
	if (is_null[v] && deg[v] == 1) return 0;
	if (is_home[v] && deg[v] == 0) return 0;
	if (s == NON) return 1;
		
	bool other_flag = false, connect = false;
	for_(i,0,W+1) {
		if (mate[i] >= IN) other_flag = true;
		if (mate[i] == s) connect = true;
	}
	
	if (!connect) {
		if (other_flag) return 0;
		if (sum_home[v+1]) return 0;
		return -1;
	}
	
	return 1;
}

int update(int i, string& mate, bool take) {
	int u = edges[i].u, v = edges[i].v;
	int ux = px[u], uy = py[u], vx = px[v], vy = py[v];
	
	if (take) {
		if (is_tree[u] || is_tree[v]) return 0;
		if (is_home[u] && is_home[v]) return 0;
		if (is_home[u] && deg[u] >= 2) return 0;
		if (is_home[v] && deg[v] >= 2) return 0;
		
		if (px[u] == px[v]) vx = W;
		
		if (mate[ux] == NON) mate[ux] = newBlock(mate);
		if (mate[vx] == NON) mate[vx] = newBlock(mate);
		if (mate[ux] == mate[vx]) return 0;
	
		merge(mate, mate[ux], mate[vx]);
	} else {
		if (is_home[u] && is_null[v] && deg[u] == 0 && deg[v] >= 1) return 0;
		if (is_home[v] && is_null[u] && deg[v] == 0 && deg[u] >= 1) return 0;
		if (px[u] != px[v] && is_null[u] && is_null[v] && mate[ux] >= IN && mate[vx] >= IN && mate[ux] != mate[vx]) return 0;
	}
	
	if (last_edge[u] == i) {
		int res = checkout(mate, u, ux, uy);
		if (res < 1) return res;
	}
	
	if (last_edge[v] == i) {
		int res = checkout(mate, v, vx, vy);
		if (res < 1) return res;
	}
	
	if (take && px[u] == px[v]) {
		mate[ux] = mate[vx];
		mate[vx] = NON;
	}
	
	return 1;
}

int fbs(int i, string mate) {
	if (i == E) return 0;
	
	hash_type hash_val = calcHash(mate);
	if (memo[i].count(hash_val)) return memo[i][hash_val];
	
	int res = MAXI;
	
	for_(b,0,2) {
		string nxt = mate;
		
		int u = edges[i].u, v = edges[i].v;
		deg[u] += b; deg[v] += b;
		
		int check = update(i, nxt, b);
		if (check == -1) res = b;
		else if (check == 1) res = min(res, fbs(i + 1, nxt) + b);
		
		deg[u] -= b; deg[v] -= b;
		
		if (res <= 1) break;
	}
	
	return memo[i][hash_val] = res;
}

void solve() {
	string init;
	for_(i,0,W+1) init += NON;
	memset(deg, 0, sizeof(deg));
	int ans = fbs(0, init);
	cout << (ans >= MAXI ? -1 : V - num_tree - ans - 1) << endl;
}

int getID(int x, int y) { return y * W + x; }

int main() {
	cin >> H >> W;
	
	for_(y,0,H) for_(x,0,W) {
		px[getID(x, y)] = x;
		py[getID(x, y)] = y;
		if (x < W - 1) edges.push_back(Edge{getID(x, y), getID(x + 1, y)});
		if (y < H - 1) edges.push_back(Edge{getID(x, y), getID(x, y + 1)});
	}
	
	V = H * W;
	E = edges.size();
	for_(i,0,E) {
		int u = edges[i].u, v = edges[i].v;
		last_edge[u] = last_edge[v] = i;
	}
	
	num_tree = 0;
	memset(is_home, 0, sizeof(is_home));
	memset(is_tree, 0, sizeof(is_tree));
	memset(is_null, 0, sizeof(is_null));
	memset(sum_home, 0, sizeof(sum_home));
	for_(y,0,H) {
		cin >> c[y];
		for_(x,0,W) {
			if (c[y][x] == '.') is_null[getID(x, y)] = true;
			if (c[y][x] == '#') is_tree[getID(x, y)] = true, ++num_tree;
			if (c[y][x] == 'H') sum_home[getID(x, y)] = is_home[getID(x, y)] = true;
		}
	}
	
	for_rev(i,V-1,1) sum_home[i-1] |= sum_home[i];
	
	solve();
}

Submission Info

Submission Time
Task D - ゆうびんやさんのお花畑
User tsukasa_diary
Language C++14 (GCC 5.4.1)
Score 50
Code Size 4340 Byte
Status MLE
Exec Time 2185 ms
Memory 110080 KB

Judge Result

Set Name small large
Score / Max Score 50 / 50 0 / 50
Status
AC × 24
AC × 54
MLE × 8
Set Name Test Cases
small a_small/a00_sample1.txt, a_small/a00_sample2.txt, a_small/a00_sample3.txt, a_small/a00_sample4.txt, a_small/a01_rand_00.txt, a_small/a01_rand_01.txt, a_small/a01_rand_02.txt, a_small/a01_rand_03.txt, a_small/a01_rand_04.txt, a_small/a01_rand_05.txt, a_small/a01_rand_06.txt, a_small/a01_rand_07.txt, a_small/a01_rand_08.txt, a_small/a01_rand_09.txt, a_small/a03_nowall_00.txt, a_small/a03_nowall_01.txt, a_small/a03_nowall_02.txt, a_small/a03_nowall_03.txt, a_small/a03_nowall_04.txt, a_small/a04_3house_00.txt, a_small/a04_3house_01.txt, a_small/a04_3house_02.txt, a_small/a04_3house_03.txt, a_small/a04_3house_04.txt
large a_small/a00_sample1.txt, a_small/a00_sample2.txt, a_small/a00_sample3.txt, a_small/a00_sample4.txt, a_small/a01_rand_00.txt, a_small/a01_rand_01.txt, a_small/a01_rand_02.txt, a_small/a01_rand_03.txt, a_small/a01_rand_04.txt, a_small/a01_rand_05.txt, a_small/a01_rand_06.txt, a_small/a01_rand_07.txt, a_small/a01_rand_08.txt, a_small/a01_rand_09.txt, a_small/a03_nowall_00.txt, a_small/a03_nowall_01.txt, a_small/a03_nowall_02.txt, a_small/a03_nowall_03.txt, a_small/a03_nowall_04.txt, a_small/a04_3house_00.txt, a_small/a04_3house_01.txt, a_small/a04_3house_02.txt, a_small/a04_3house_03.txt, a_small/a04_3house_04.txt, b_large/b00_sample5.txt, b_large/b01_rand_00.txt, b_large/b01_rand_01.txt, b_large/b01_rand_02.txt, b_large/b01_rand_03.txt, b_large/b01_rand_04.txt, b_large/b01_rand_05.txt, b_large/b01_rand_06.txt, b_large/b01_rand_07.txt, b_large/b01_rand_08.txt, b_large/b01_rand_09.txt, b_large/b02_maxrand_00.txt, b_large/b02_maxrand_01.txt, b_large/b02_maxrand_02.txt, b_large/b02_maxrand_03.txt, b_large/b02_maxrand_04.txt, b_large/b03_nowall_00.txt, b_large/b03_nowall_01.txt, b_large/b03_nowall_02.txt, b_large/b03_nowall_03.txt, b_large/b03_nowall_04.txt, b_large/b04_3house_00.txt, b_large/b04_3house_01.txt, b_large/b04_3house_02.txt, b_large/b04_3house_03.txt, b_large/b04_3house_04.txt, b_large/b05_handmade_01.txt, b_large/b05_handmade_02.txt, b_large/b05_handmade_03.txt, b_large/b05_handmade_04.txt, b_large/b05_handmade_05.txt, b_large/b05_handmade_06.txt, b_large/b05_handmade_07.txt, b_large/b05_handmade_08.txt, b_large/b05_handmade_09.txt, b_large/b05_handmade_10.txt, b_large/b05_handmade_maxhouse.txt, b_large/b05_handmade_retmax.txt
Case Name Status Exec Time Memory
a_small/a00_sample1.txt AC 1 ms 256 KB
a_small/a00_sample2.txt AC 1 ms 256 KB
a_small/a00_sample3.txt AC 1 ms 256 KB
a_small/a00_sample4.txt AC 1 ms 256 KB
a_small/a01_rand_00.txt AC 1 ms 256 KB
a_small/a01_rand_01.txt AC 1 ms 256 KB
a_small/a01_rand_02.txt AC 1 ms 256 KB
a_small/a01_rand_03.txt AC 1 ms 256 KB
a_small/a01_rand_04.txt AC 1 ms 256 KB
a_small/a01_rand_05.txt AC 1 ms 256 KB
a_small/a01_rand_06.txt AC 1 ms 256 KB
a_small/a01_rand_07.txt AC 1 ms 256 KB
a_small/a01_rand_08.txt AC 1 ms 256 KB
a_small/a01_rand_09.txt AC 1 ms 256 KB
a_small/a03_nowall_00.txt AC 1 ms 256 KB
a_small/a03_nowall_01.txt AC 1 ms 256 KB
a_small/a03_nowall_02.txt AC 1 ms 256 KB
a_small/a03_nowall_03.txt AC 1 ms 256 KB
a_small/a03_nowall_04.txt AC 1 ms 256 KB
a_small/a04_3house_00.txt AC 1 ms 256 KB
a_small/a04_3house_01.txt AC 1 ms 256 KB
a_small/a04_3house_02.txt AC 1 ms 256 KB
a_small/a04_3house_03.txt AC 1 ms 256 KB
a_small/a04_3house_04.txt AC 1 ms 256 KB
b_large/b00_sample5.txt AC 7 ms 768 KB
b_large/b01_rand_00.txt AC 1 ms 256 KB
b_large/b01_rand_01.txt AC 86 ms 5376 KB
b_large/b01_rand_02.txt AC 212 ms 12672 KB
b_large/b01_rand_03.txt AC 2 ms 384 KB
b_large/b01_rand_04.txt AC 7 ms 768 KB
b_large/b01_rand_05.txt AC 2 ms 384 KB
b_large/b01_rand_06.txt AC 5 ms 640 KB
b_large/b01_rand_07.txt AC 1 ms 256 KB
b_large/b01_rand_08.txt AC 18 ms 1536 KB
b_large/b01_rand_09.txt AC 2 ms 384 KB
b_large/b02_maxrand_00.txt AC 23 ms 1920 KB
b_large/b02_maxrand_01.txt AC 22 ms 1920 KB
b_large/b02_maxrand_02.txt AC 41 ms 2560 KB
b_large/b02_maxrand_03.txt MLE 1324 ms 65280 KB
b_large/b02_maxrand_04.txt MLE 1793 ms 88576 KB
b_large/b03_nowall_00.txt AC 1159 ms 60416 KB
b_large/b03_nowall_01.txt AC 592 ms 32256 KB
b_large/b03_nowall_02.txt MLE 1476 ms 74112 KB
b_large/b03_nowall_03.txt MLE 1786 ms 86784 KB
b_large/b03_nowall_04.txt MLE 1803 ms 88064 KB
b_large/b04_3house_00.txt AC 19 ms 1536 KB
b_large/b04_3house_01.txt AC 194 ms 12800 KB
b_large/b04_3house_02.txt AC 210 ms 13056 KB
b_large/b04_3house_03.txt AC 160 ms 9984 KB
b_large/b04_3house_04.txt AC 217 ms 13696 KB
b_large/b05_handmade_01.txt AC 44 ms 3328 KB
b_large/b05_handmade_02.txt MLE 2185 ms 110080 KB
b_large/b05_handmade_03.txt AC 61 ms 4224 KB
b_large/b05_handmade_04.txt MLE 1475 ms 72704 KB
b_large/b05_handmade_05.txt AC 613 ms 33920 KB
b_large/b05_handmade_06.txt AC 788 ms 41728 KB
b_large/b05_handmade_07.txt AC 1005 ms 56960 KB
b_large/b05_handmade_08.txt AC 13 ms 1280 KB
b_large/b05_handmade_09.txt AC 582 ms 33408 KB
b_large/b05_handmade_10.txt AC 46 ms 3328 KB
b_large/b05_handmade_maxhouse.txt AC 2 ms 384 KB
b_large/b05_handmade_retmax.txt MLE 1428 ms 71680 KB