Submission #1419027


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];
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 (c[vy][vx] == '.' && deg[v] == 1) return 0;
	if (c[vy][vx] == 'H' && deg[v] != 1) 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 (is_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 (c[uy][ux] == '#' || c[vy][vx] == '#') return 0;
		if (c[uy][ux] == 'H' && c[vy][vx] == 'H') return 0;
	
		if (px[u] == px[v]) vx = W;
		
		if (mate[ux] == NON) mate[ux] = newBlock(mate);
		else if (c[uy][ux] == 'H') return 0;
	
		if (mate[vx] == NON) mate[vx] = newBlock(mate);
		else if (c[vy][vx] == 'H') return 0;
	
		if (mate[ux] == mate[vx]) return 0;
	
		merge(mate, mate[ux], mate[vx]);
	}
		
	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;
	}
	
	if (ux == W - 1) {
		for_(j,0,W) {
			if (mate[j] >= IN && mate[j] == mate[j+1] &&
				c[vy][j] == '.' && c[vy][j + 1] == '.') return 0;
		}
	}	
	
	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));
	for_(y,0,H) {
		cin >> c[y];
		for_(x,0,W) {
			if (c[y][x] == '#') ++num_tree;
			if (c[y][x] == 'H') is_home[getID(x, y)] = true;
		}
	}
	
	for_rev(i,V-1,1) is_home[i-1] |= is_home[i];
	
	solve();
}

Submission Info

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

Judge Result

Set Name small large
Score / Max Score 50 / 50 0 / 50
Status
AC × 24
AC × 50
TLE × 5
MLE × 7
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 9 ms 768 KB
b_large/b01_rand_00.txt AC 1 ms 256 KB
b_large/b01_rand_01.txt AC 275 ms 14336 KB
b_large/b01_rand_02.txt AC 736 ms 35584 KB
b_large/b01_rand_03.txt AC 2 ms 384 KB
b_large/b01_rand_04.txt AC 6 ms 640 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 2 ms 256 KB
b_large/b01_rand_08.txt AC 17 ms 1408 KB
b_large/b01_rand_09.txt AC 2 ms 384 KB
b_large/b02_maxrand_00.txt AC 35 ms 2688 KB
b_large/b02_maxrand_01.txt AC 26 ms 2176 KB
b_large/b02_maxrand_02.txt AC 44 ms 3072 KB
b_large/b02_maxrand_03.txt TLE 5269 ms 218424 KB
b_large/b02_maxrand_04.txt MLE 4800 ms 187972 KB
b_large/b03_nowall_00.txt TLE 5071 ms 209680 KB
b_large/b03_nowall_01.txt MLE 3220 ms 139692 KB
b_large/b03_nowall_02.txt MLE 3991 ms 161696 KB
b_large/b03_nowall_03.txt TLE 5268 ms 219304 KB
b_large/b03_nowall_04.txt TLE 5266 ms 212212 KB
b_large/b04_3house_00.txt AC 27 ms 2048 KB
b_large/b04_3house_01.txt AC 223 ms 13440 KB
b_large/b04_3house_02.txt AC 185 ms 11776 KB
b_large/b04_3house_03.txt AC 196 ms 11520 KB
b_large/b04_3house_04.txt AC 317 ms 18852 KB
b_large/b05_handmade_01.txt AC 68 ms 4608 KB
b_large/b05_handmade_02.txt MLE 3010 ms 133564 KB
b_large/b05_handmade_03.txt AC 82 ms 5632 KB
b_large/b05_handmade_04.txt MLE 3789 ms 156616 KB
b_large/b05_handmade_05.txt AC 1003 ms 47232 KB
b_large/b05_handmade_06.txt MLE 1354 ms 66840 KB
b_large/b05_handmade_07.txt AC 1025 ms 52096 KB
b_large/b05_handmade_08.txt AC 14 ms 1280 KB
b_large/b05_handmade_09.txt TLE 5270 ms 241204 KB
b_large/b05_handmade_10.txt AC 329 ms 18432 KB
b_large/b05_handmade_maxhouse.txt AC 229 ms 14464 KB
b_large/b05_handmade_retmax.txt MLE 3176 ms 126556 KB