Submission #136391

# Submission time Handle Problem Language Result Execution time Memory
136391 2019-07-25T08:25:54 Z 윤교준(#3260) Connect (CEOI06_connect) C++14
76 / 100
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