oj.uz

Submission #136399

# Submission time Handle Problem Language Result Execution time Memory
136399 2019-07-25T08:36:40 Z 윤교준(#3260) Connect (CEOI06_connect) C++14
8 / 100
 34 ms 1624 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++) {
			if(isX[s][x]) continue;
			C[s][s][x] = true;
			for(int e = s+1; e < H; e++) {
				if(!B[e][x][0] || isX[e][x]) 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;
		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;
			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);
				}
			}
		}

		for(int h = H-1; h; h--) {
			for(int key = 1<<H; key--;) if(key & (1<<h)) {
				int t = dp[x+1][key];
				if(INF <= t) continue;
				if((key & (1<<(h-1))) || !B[h][x][0] || isX[h-1][x]) continue;
				upmin(dp[x+1][key ^ (1<<h) ^ (1<<(h-1))], t + 2);
			}
		}
		for(int h = 0; h+1 < H; h++) {
			for(int key = 0; key < (1<<H); key++) if(key & (1<<h)) {
				int t = dp[x+1][key];
				if(INF <= t) continue;
				if((key & (1<<(h+1))) || !B[h][x][2] || isX[h+1][x]) continue;
				upmin(dp[x+1][key ^ (1<<h) ^ (1<<(h+1))], t + 2);
			}
		}

		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);
			}
		}
	}

	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
8.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 1528 KB Wrong score! (1061109564, expected 26)
2 Incorrect 4 ms 1528 KB Wrong score! (1061109563, expected 40)
3 Incorrect 4 ms 1528 KB Wrong score! (1061109555, expected 74)
4 Incorrect 4 ms 1528 KB Wrong score! (1061109561, expected 28)
5 Incorrect 6 ms 1528 KB Wrong score! (1061109527, expected 102)
6 Incorrect 4 ms 1528 KB Wrong score! (1061109548, expected 112)
7 Incorrect 4 ms 1528 KB Wrong score! (76, expected 72)
8 Partially correct 5 ms 1528 KB Partially correct (80% score). Wrong board
9 Incorrect 5 ms 1528 KB Wrong score! (148, expected 132)
10 Incorrect 4 ms 1532 KB Wrong score! (1061109492, expected 208)
11 Incorrect 6 ms 1528 KB Wrong score! (114, expected 106)
12 Incorrect 5 ms 1528 KB Wrong score! (1061109467, expected 268)
13 Incorrect 5 ms 1528 KB Wrong score! (1061109486, expected 208)
14 Incorrect 5 ms 1528 KB Wrong score! (1061109527, expected 462)
15 Incorrect 6 ms 1528 KB Wrong score! (1061109540, expected 422)
16 Partially correct 17 ms 1624 KB Partially correct (80% score). Wrong board
17 Incorrect 9 ms 1528 KB Wrong score! (1061109546, expected 288)
18 Incorrect 9 ms 1528 KB Wrong score! (1061109532, expected 296)
19 Incorrect 34 ms 1528 KB Wrong score! (232, expected 212)
20 Incorrect 9 ms 1580 KB Wrong score! (1061109417, expected 374)