Submission #1419040


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]);
	} else {
		if (c[uy][ux] == 'H' && c[vx][vy] == '.' && deg[u] == 0 && deg[v] >= 1) return 0;
		if (c[vy][vx] == 'H' && c[ux][uy] == '.' && deg[v] == 0 && deg[u] >= 1) 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));
	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 0
Code Size 4007 Byte
Status WA
Exec Time 5271 ms
Memory 251268 KB

Judge Result

Set Name small large
Score / Max Score 0 / 50 0 / 50
Status
AC × 19
WA × 5
AC × 39
WA × 13
TLE × 5
MLE × 5
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 WA 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 WA 1 ms 256 KB
a_small/a01_rand_07.txt WA 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 WA 1 ms 256 KB
a_small/a03_nowall_04.txt WA 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 8 ms 768 KB
b_large/b01_rand_00.txt AC 1 ms 256 KB
b_large/b01_rand_01.txt AC 242 ms 13568 KB
b_large/b01_rand_02.txt AC 701 ms 36480 KB
b_large/b01_rand_03.txt AC 2 ms 384 KB
b_large/b01_rand_04.txt AC 8 ms 768 KB
b_large/b01_rand_05.txt AC 3 ms 384 KB
b_large/b01_rand_06.txt WA 5 ms 512 KB
b_large/b01_rand_07.txt AC 2 ms 256 KB
b_large/b01_rand_08.txt AC 24 ms 1920 KB
b_large/b01_rand_09.txt AC 2 ms 256 KB
b_large/b02_maxrand_00.txt WA 34 ms 2688 KB
b_large/b02_maxrand_01.txt AC 33 ms 2688 KB
b_large/b02_maxrand_02.txt AC 62 ms 4480 KB
b_large/b02_maxrand_03.txt WA 34 ms 2432 KB
b_large/b02_maxrand_04.txt TLE 5270 ms 246452 KB
b_large/b03_nowall_00.txt MLE 3477 ms 161360 KB
b_large/b03_nowall_01.txt AC 1 ms 256 KB
b_large/b03_nowall_02.txt MLE 4061 ms 189092 KB
b_large/b03_nowall_03.txt TLE 5271 ms 247828 KB
b_large/b03_nowall_04.txt TLE 5271 ms 246048 KB
b_large/b04_3house_00.txt AC 27 ms 2048 KB
b_large/b04_3house_01.txt WA 1 ms 256 KB
b_large/b04_3house_02.txt AC 359 ms 21888 KB
b_large/b04_3house_03.txt AC 276 ms 17292 KB
b_large/b04_3house_04.txt AC 388 ms 23472 KB
b_large/b05_handmade_01.txt AC 75 ms 5632 KB
b_large/b05_handmade_02.txt TLE 5271 ms 251268 KB
b_large/b05_handmade_03.txt AC 119 ms 7808 KB
b_large/b05_handmade_04.txt TLE 5270 ms 235512 KB
b_large/b05_handmade_05.txt WA 9 ms 768 KB
b_large/b05_handmade_06.txt WA 7 ms 640 KB
b_large/b05_handmade_07.txt MLE 2051 ms 108928 KB
b_large/b05_handmade_08.txt AC 16 ms 1408 KB
b_large/b05_handmade_09.txt MLE 1265 ms 67248 KB
b_large/b05_handmade_10.txt WA 7 ms 768 KB
b_large/b05_handmade_maxhouse.txt WA 36 ms 2688 KB
b_large/b05_handmade_retmax.txt MLE 4806 ms 205944 KB