oj.uz

답안 #136382

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
136382 2019-07-25T08:09:42 Z 윤교준(#3260) Connect (CEOI06_connect) C++14
24 / 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(y && !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));
		}
		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(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);
                             ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
24.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 1528 KB Wrong score! (22, expected 26)
2 Incorrect 5 ms 1528 KB Wrong score! (24, expected 40)
3 Incorrect 4 ms 1528 KB Wrong score! (70, expected 74)
4 Partially correct 5 ms 1532 KB Partially correct (80% score). Wrong board
5 Incorrect 18 ms 1656 KB Wrong score! (98, expected 102)
6 Incorrect 4 ms 1528 KB Wrong score! (100, expected 112)
7 Partially correct 4 ms 1528 KB Partially correct (80% score). Wrong board
8 Incorrect 5 ms 1528 KB Wrong score! (66, expected 94)
9 Incorrect 6 ms 1528 KB Wrong score! (108, expected 132)
10 Partially correct 6 ms 1528 KB Partially correct (80% score). Wrong board
11 Incorrect 7 ms 1528 KB Wrong score! (94, expected 106)
12 Partially correct 8 ms 1528 KB Partially correct (80% score). Wrong board
13 Incorrect 11 ms 1532 KB Wrong score! (204, expected 208)
14 Incorrect 6 ms 1528 KB Wrong score! (406, expected 462)
15 Incorrect 6 ms 1528 KB Wrong score! (390, expected 422)
16 Incorrect 24 ms 1528 KB Wrong score! (428, expected 664)
17 Incorrect 16 ms 1528 KB Wrong score! (200, expected 288)
18 Incorrect 36 ms 1652 KB Wrong score! (280, expected 296)
19 Partially correct 47 ms 1656 KB Partially correct (80% score). Wrong board
20 Partially correct 38 ms 1656 KB Partially correct (80% score). Wrong board