Submission #1419066
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;
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] && deg[u] >= 2) return 0;
if (is_home[v] && deg[v] >= 2) return 0;
if (px[u] == px[v]) 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 (px[u] != px[v] && is_null[u] && is_null[v] && mate[ux] >= IN && mate[vx] >= IN) 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 |
50 |
Code Size |
4322 Byte |
Status |
MLE |
Exec Time |
2256 ms |
Memory |
110080 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 |
7 ms |
768 KB |
b_large/b01_rand_00.txt |
AC |
1 ms |
256 KB |
b_large/b01_rand_01.txt |
AC |
86 ms |
5376 KB |
b_large/b01_rand_02.txt |
AC |
213 ms |
12672 KB |
b_large/b01_rand_03.txt |
AC |
2 ms |
384 KB |
b_large/b01_rand_04.txt |
AC |
7 ms |
768 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 |
1 ms |
256 KB |
b_large/b01_rand_08.txt |
AC |
18 ms |
1536 KB |
b_large/b01_rand_09.txt |
AC |
2 ms |
384 KB |
b_large/b02_maxrand_00.txt |
AC |
22 ms |
1920 KB |
b_large/b02_maxrand_01.txt |
AC |
22 ms |
1920 KB |
b_large/b02_maxrand_02.txt |
AC |
34 ms |
2560 KB |
b_large/b02_maxrand_03.txt |
MLE |
1360 ms |
65920 KB |
b_large/b02_maxrand_04.txt |
MLE |
1768 ms |
88448 KB |
b_large/b03_nowall_00.txt |
AC |
1117 ms |
60416 KB |
b_large/b03_nowall_01.txt |
AC |
575 ms |
32256 KB |
b_large/b03_nowall_02.txt |
MLE |
1487 ms |
74240 KB |
b_large/b03_nowall_03.txt |
MLE |
1763 ms |
86784 KB |
b_large/b03_nowall_04.txt |
MLE |
1833 ms |
88064 KB |
b_large/b04_3house_00.txt |
AC |
19 ms |
1536 KB |
b_large/b04_3house_01.txt |
AC |
195 ms |
12800 KB |
b_large/b04_3house_02.txt |
AC |
207 ms |
13056 KB |
b_large/b04_3house_03.txt |
AC |
157 ms |
9984 KB |
b_large/b04_3house_04.txt |
AC |
219 ms |
13696 KB |
b_large/b05_handmade_01.txt |
AC |
43 ms |
3328 KB |
b_large/b05_handmade_02.txt |
MLE |
2256 ms |
110080 KB |
b_large/b05_handmade_03.txt |
AC |
60 ms |
4224 KB |
b_large/b05_handmade_04.txt |
MLE |
1466 ms |
72704 KB |
b_large/b05_handmade_05.txt |
AC |
610 ms |
33792 KB |
b_large/b05_handmade_06.txt |
AC |
794 ms |
41728 KB |
b_large/b05_handmade_07.txt |
AC |
1009 ms |
56960 KB |
b_large/b05_handmade_08.txt |
AC |
13 ms |
1280 KB |
b_large/b05_handmade_09.txt |
AC |
603 ms |
32768 KB |
b_large/b05_handmade_10.txt |
AC |
47 ms |
3328 KB |
b_large/b05_handmade_maxhouse.txt |
AC |
2 ms |
384 KB |
b_large/b05_handmade_retmax.txt |
MLE |
1422 ms |
71808 KB |