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