Submission #1419345
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 long long hash_type;
typedef int16_t cost_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 << 4) | 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] && mate[ux] >= IN) return 0;
if (px[u] != px[v] && is_home[v] && mate[vx] >= IN) return 0;
if (px[u] == px[v]) {
if (ux > 0 && mate[ux - 1] >= IN && is_null[v - 1] && is_home[v]) return 0;
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 (is_null[u] && is_null[v] && deg[u] >= 1 && deg[v] >= 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));
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 |
0 |
Code Size |
4431 Byte |
Status |
WA |
Exec Time |
2260 ms |
Memory |
109568 KB |
Judge Result
Set Name |
small |
large |
Score / Max Score |
0 / 50 |
0 / 50 |
Status |
|
|
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 |
3 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 |
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 |
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 |
43 ms |
2816 KB |
b_large/b01_rand_02.txt |
WA |
135 ms |
8192 KB |
b_large/b01_rand_03.txt |
AC |
2 ms |
384 KB |
b_large/b01_rand_04.txt |
WA |
7 ms |
640 KB |
b_large/b01_rand_05.txt |
AC |
2 ms |
384 KB |
b_large/b01_rand_06.txt |
AC |
5 ms |
512 KB |
b_large/b01_rand_07.txt |
AC |
1 ms |
256 KB |
b_large/b01_rand_08.txt |
AC |
18 ms |
1408 KB |
b_large/b01_rand_09.txt |
AC |
2 ms |
256 KB |
b_large/b02_maxrand_00.txt |
AC |
15 ms |
1280 KB |
b_large/b02_maxrand_01.txt |
WA |
22 ms |
1792 KB |
b_large/b02_maxrand_02.txt |
AC |
30 ms |
2304 KB |
b_large/b02_maxrand_03.txt |
AC |
1312 ms |
61440 KB |
b_large/b02_maxrand_04.txt |
MLE |
1704 ms |
80896 KB |
b_large/b03_nowall_00.txt |
AC |
693 ms |
36736 KB |
b_large/b03_nowall_01.txt |
AC |
215 ms |
13056 KB |
b_large/b03_nowall_02.txt |
MLE |
1339 ms |
66048 KB |
b_large/b03_nowall_03.txt |
MLE |
1560 ms |
75264 KB |
b_large/b03_nowall_04.txt |
MLE |
1632 ms |
77568 KB |
b_large/b04_3house_00.txt |
AC |
16 ms |
1408 KB |
b_large/b04_3house_01.txt |
AC |
183 ms |
11904 KB |
b_large/b04_3house_02.txt |
AC |
207 ms |
12928 KB |
b_large/b04_3house_03.txt |
AC |
154 ms |
9600 KB |
b_large/b04_3house_04.txt |
AC |
178 ms |
11392 KB |
b_large/b05_handmade_01.txt |
AC |
30 ms |
2432 KB |
b_large/b05_handmade_02.txt |
MLE |
2260 ms |
109568 KB |
b_large/b05_handmade_03.txt |
AC |
61 ms |
4224 KB |
b_large/b05_handmade_04.txt |
MLE |
1501 ms |
72704 KB |
b_large/b05_handmade_05.txt |
AC |
616 ms |
33792 KB |
b_large/b05_handmade_06.txt |
AC |
818 ms |
41728 KB |
b_large/b05_handmade_07.txt |
AC |
1006 ms |
56960 KB |
b_large/b05_handmade_08.txt |
AC |
13 ms |
1280 KB |
b_large/b05_handmade_09.txt |
AC |
31 ms |
2176 KB |
b_large/b05_handmade_10.txt |
WA |
3 ms |
384 KB |
b_large/b05_handmade_maxhouse.txt |
WA |
1 ms |
256 KB |
b_large/b05_handmade_retmax.txt |
MLE |
1405 ms |
67456 KB |