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 |
× 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 |