Submission #1419024
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]) {
if (ux > 0 && mate[ux] >= IN && mate[ux - 1] >= IN && c[vy][vx + 1] == 'H') return 0;
if (vx < W - 1 && deg[u] == 1 && mate[W + 1] && c[vy][vx + 1] == '.') return 0;
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;
}
mate[W + 1] = take;
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+2) 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 |
4035 Byte |
Status |
WA |
Exec Time |
5270 ms |
Memory |
243308 KB |
Judge Result
Set Name |
small |
large |
Score / Max Score |
50 / 50 |
0 / 50 |
Status |
|
AC |
× 47 |
WA |
× 2 |
TLE |
× 8 |
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 |
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 |
13 ms |
1152 KB |
b_large/b01_rand_00.txt |
AC |
1 ms |
256 KB |
b_large/b01_rand_01.txt |
AC |
279 ms |
14848 KB |
b_large/b01_rand_02.txt |
AC |
457 ms |
24192 KB |
b_large/b01_rand_03.txt |
AC |
2 ms |
384 KB |
b_large/b01_rand_04.txt |
AC |
10 ms |
896 KB |
b_large/b01_rand_05.txt |
AC |
3 ms |
384 KB |
b_large/b01_rand_06.txt |
AC |
6 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 |
38 ms |
2944 KB |
b_large/b02_maxrand_01.txt |
AC |
40 ms |
3328 KB |
b_large/b02_maxrand_02.txt |
AC |
71 ms |
4864 KB |
b_large/b02_maxrand_03.txt |
TLE |
5269 ms |
222416 KB |
b_large/b02_maxrand_04.txt |
TLE |
5270 ms |
237992 KB |
b_large/b03_nowall_00.txt |
MLE |
3333 ms |
149204 KB |
b_large/b03_nowall_01.txt |
MLE |
2849 ms |
128008 KB |
b_large/b03_nowall_02.txt |
TLE |
5270 ms |
239812 KB |
b_large/b03_nowall_03.txt |
TLE |
5270 ms |
234356 KB |
b_large/b03_nowall_04.txt |
TLE |
5269 ms |
237088 KB |
b_large/b04_3house_00.txt |
AC |
34 ms |
2560 KB |
b_large/b04_3house_01.txt |
AC |
417 ms |
24320 KB |
b_large/b04_3house_02.txt |
AC |
405 ms |
21888 KB |
b_large/b04_3house_03.txt |
AC |
368 ms |
20236 KB |
b_large/b04_3house_04.txt |
AC |
406 ms |
23552 KB |
b_large/b05_handmade_01.txt |
AC |
102 ms |
6912 KB |
b_large/b05_handmade_02.txt |
TLE |
5270 ms |
243308 KB |
b_large/b05_handmade_03.txt |
AC |
124 ms |
8064 KB |
b_large/b05_handmade_04.txt |
TLE |
5269 ms |
227576 KB |
b_large/b05_handmade_05.txt |
MLE |
2082 ms |
98560 KB |
b_large/b05_handmade_06.txt |
MLE |
1293 ms |
63360 KB |
b_large/b05_handmade_07.txt |
MLE |
1963 ms |
98048 KB |
b_large/b05_handmade_08.txt |
AC |
18 ms |
1536 KB |
b_large/b05_handmade_09.txt |
AC |
1173 ms |
58496 KB |
b_large/b05_handmade_10.txt |
WA |
58 ms |
3840 KB |
b_large/b05_handmade_maxhouse.txt |
WA |
7 ms |
768 KB |
b_large/b05_handmade_retmax.txt |
TLE |
5265 ms |
212856 KB |