| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 136391 |
2019-07-25T08:25:54 Z |
윤교준(#3260) |
Connect (CEOI06_connect) |
C++14 |
|
47 ms |
1656 KB |
#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define upmin(a,b) (a)=min((a),(b))
#define INF (0x3f3f3f3f)
using namespace std;
typedef pair<int, int> pii;
const bool debug = 0;
int dp[40][1<<12];
bool C[12][12][39], D[1<<12][12][12];
bool B[12][39][4], isX[12][39];
char A[25][80];
int H, W, Ans;
int main() {
scanf("%d%d ", &H, &W);
for(int i = 0; i < H; i++) fgets(A[i], INF, stdin);
H >>= 1; W >>= 1;
for(int i = 0; i < H; i++) for(int j = 0; j < W; j++) {
int y = i<<1|1, x = j<<1|1;
if(' ' == A[y-1][x]) B[i][j][0] = true;
if(' ' == A[y][x+1]) B[i][j][1] = true;
if(' ' == A[y+1][x]) B[i][j][2] = true;
if(' ' == A[y][x-1]) B[i][j][3] = true;
isX[i][j] = 'X' == A[y][x];
}
for(int x = 0; x < W; x++) {
for(int s = 0; s < H; s++) {
C[s][s][x] = true;
for(int e = s+1; e < H; e++) {
if(!B[e][x][0]) break;
C[s][e][x] = true;
}
}
}
for(int key = 0; key < (1<<12); key++) {
for(int s = 0; s < 12; s++) for(int e = s; e < 12; e++) {
D[key][s][e] = true;
for(int i = s; i <= e; i++) {
if(key & (1<<i)) {
D[key][s][e] = false;
break;
}
}
}
}
fill(dp[0], dp[39]+(1<<12), INF);
dp[0][0] = 0;
for(int x = 0; x < W; x++) {
int xkey = 0, bkey = 0;
for(int y = 0; y < H; y++) if(isX[y][x]) xkey |= 1<<y;
for(int y = 0; y < H; y++) if(x && !B[y][x][3]) bkey |= 1<<y;
if(debug) printf("x=%d, xkey=%d, bkey=%d\n", x, xkey, bkey);
for(int key = 0; key < (1<<H); key++) if(!(key&bkey)) {
upmin(dp[x+1][key^xkey], dp[x][key] + (__builtin_popcount(key) << 1)
+ __builtin_popcount((xkey^key)&xkey));
if(debug) {
printf("%d -> %d : %d -> %d\n", key, key^xkey, dp[x][key], dp[x+1][key^xkey]);
}
}
for(int key = 0; key < (1<<H); key++) {
int t = dp[x+1][key];
if(INF <= t) continue;
if(debug) printf("x+1=%d, key=%d, t=%d\n", x+1, key, t);
for(int s = 0; s < H; s++) {
for(int e = s+1; e < H; e++) {
if(!C[s][e][x] || !D[key][s][e]) break;
upmin(dp[x+1][key | 1<<s | 1<<e], dp[x+1][key] + ((e-s)<<1) + 1);
}
}
}
priority_queue<pii, vector<pii>, greater<pii>> PQ;
for(int key = 0; key < (1<<H); key++) {
int t = dp[x+1][key];
if(INF <= t) continue;
PQ.emplace(t, key);
}
for(int key, dst; !PQ.empty();) {
tie(dst, key) = PQ.top(); PQ.pop();
if(dp[x+1][key] < dst) continue;
if(debug) printf("PQ x+1=%d, key=%d, dst=%d\n", x+1, key, dst);
dst += 2;
for(int i = 0; i < H; i++) if(key & (1<<i)) {
if(i && !(key & (1<<(i-1))) && B[i][x][0]) {
int nkey = (key ^ (1<<i)) | (1<<(i-1));
if(dst < dp[x+1][nkey]) {
dp[x+1][nkey] = dst;
PQ.emplace(dst, nkey);
}
}
if(i+1 < H && !(key & (1<<(i+1))) && B[i][x][2]) {
int nkey = (key ^ (1<<i)) | (1<<(i+1));
if(dst < dp[x+1][nkey]) {
dp[x+1][nkey] = dst;
PQ.emplace(dst, nkey);
}
}
}
}
for(int key = 1<<H; key--;) {
int t = dp[x+1][key];
if(INF <= t) continue;
vector<int> V;
for(int i = 0; i < H; i++) if(key & (1<<i)) V.eb(i);
int n = sz(V);
for(int i = 1, s, e; i < n; i++) {
s = V[i-1]; e = V[i];
if(!C[s][e][x]) continue;
upmin(dp[x+1][key ^ (1<<s) ^ (1<<e)], t + ((e-s)<<1) - 1);
if(x+1 == 6 && 64 == (key ^ (1<<s) ^ (1<<e))) {
}
}
if(debug) printf("MERGE x+1=%d, key=%d, t=%d\n", x+1, key, t);
}
if(debug) puts("\n\n");
}
Ans = dp[W][0];
int xcnt = 0;
for(int i = 0; i < H; i++) for(int j = 0; j < W; j++) if(isX[i][j]) xcnt++;
Ans -= xcnt >> 1;
cout << Ans << endl;
return 0;
}
Compilation message
connect.cpp: In function 'int main()':
connect.cpp:24:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d ", &H, &W);
~~~~~^~~~~~~~~~~~~~~~~
connect.cpp:25:34: warning: ignoring return value of 'char* fgets(char*, int, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
for(int i = 0; i < H; i++) fgets(A[i], INF, stdin);
~~~~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
5 ms |
1528 KB |
Partially correct (80% score). Wrong board |
| 2 |
Partially correct |
5 ms |
1528 KB |
Partially correct (80% score). Wrong board |
| 3 |
Partially correct |
5 ms |
1528 KB |
Partially correct (80% score). Wrong board |
| 4 |
Partially correct |
5 ms |
1528 KB |
Partially correct (80% score). Wrong board |
| 5 |
Partially correct |
18 ms |
1656 KB |
Partially correct (80% score). Wrong board |
| 6 |
Partially correct |
4 ms |
1528 KB |
Partially correct (80% score). Wrong board |
| 7 |
Partially correct |
5 ms |
1528 KB |
Partially correct (80% score). Wrong board |
| 8 |
Partially correct |
5 ms |
1528 KB |
Partially correct (80% score). Wrong board |
| 9 |
Partially correct |
5 ms |
1528 KB |
Partially correct (80% score). Wrong board |
| 10 |
Partially correct |
7 ms |
1528 KB |
Partially correct (80% score). Wrong board |
| 11 |
Partially correct |
6 ms |
1500 KB |
Partially correct (80% score). Wrong board |
| 12 |
Partially correct |
8 ms |
1528 KB |
Partially correct (80% score). Wrong board |
| 13 |
Partially correct |
10 ms |
1528 KB |
Partially correct (80% score). Wrong board |
| 14 |
Partially correct |
6 ms |
1528 KB |
Partially correct (80% score). Wrong board |
| 15 |
Incorrect |
6 ms |
1528 KB |
Wrong score! (418, expected 422) |
| 16 |
Partially correct |
22 ms |
1500 KB |
Partially correct (80% score). Wrong board |
| 17 |
Partially correct |
15 ms |
1656 KB |
Partially correct (80% score). Wrong board |
| 18 |
Partially correct |
33 ms |
1656 KB |
Partially correct (80% score). Wrong board |
| 19 |
Partially correct |
47 ms |
1656 KB |
Partially correct (80% score). Wrong board |
| 20 |
Partially correct |
39 ms |
1656 KB |
Partially correct (80% score). Wrong board |
