oj.uz

Submission #136347

# Submission time Handle Problem Language Result Execution time Memory
136347 2019-07-25T07:23:21 Z 조승현(#3264) Connect (CEOI06_connect) C++14
80 / 100
 27 ms 17016 KB 
#include<cstdio>
#include<algorithm>
#include<vector>
char p[30][100];
int W, H, n, m, chk[15][50];
int D[15][50][1 << 13], w[15][50][4];
int dx[4] = { 0,1,0,-1 }, dy[4] = { 1,0,-1,0 };
void Do(int *T, int *D, int x, int y) {
	int i, Full = (1 << (n + 1)) - 1;
	for (i = 0; i < (1 << (n + 1)); i++) {
		if (T[i] > 8e8)continue;
		int c = 0;
		if ((i & 1))c++;
		if ((i >> n) & 1)c++;
		int mask = ((i&(~1)) << 1)&Full;
		if (chk[x][y]) {
			if (c == 2)continue;
			if (c == 1) {
				if (D[mask] > T[i]) {
					D[mask] = T[i];
				}
			}
			else {
				if (w[x][y][0]) {
					if (D[mask | 2] > T[i]) {
						D[mask | 2] = T[i];
					}
				}
				if (w[x][y][1]) {
					if (D[mask | 1] > T[i]) {
						D[mask | 1] = T[i];
					}
				}
			}
			continue;
		}
		if (c == 1) {
			if (w[x][y][0]) {
				if (D[mask | 2] > T[i] + 1) {
					D[mask | 2] = T[i] + 1;
				}
			}
			if (w[x][y][1]) {
				if (D[mask | 1] > T[i] + 1) {
					D[mask | 1] = T[i] + 1;
				}
			}
		}
		if (c == 2) {
			if (D[mask] > T[i] + 1) {
				D[mask] = T[i] + 1;
			}
		}
		if (c == 0) {
			if (D[mask] > T[i]) {
				D[mask] = T[i];
			}
			if (w[x][y][0] && w[x][y][1]) {
				if (D[mask | 3] > T[i] + 1) {
					D[mask | 3] = T[i] + 1;
				}
			}
		}
	}
}
int main() {
	//freopen("input.txt", "r", stdin);
	int i, j, k;
	scanf("%d%d", &W, &H);
	fgets(p[0], 90, stdin);
	for (i = 1; i <= W; i++) {
		fgets(p[i]+1, 90, stdin);
	}
	n = W / 2, m = H / 2;
	int c = 0;
	for (i = 1; i <= n; i++) {
		for (j = 1; j <= m; j++) {
			if (i != n && p[i * 2 + 1][j * 2] != '-') {
				w[i][j][1] = w[i + 1][j][3] = 1;
			}
			if (j != m && p[i * 2][j * 2 + 1] != '|') {
				w[i][j][0] = w[i][j + 1][2] = 1;
			}
			if (p[i * 2][j * 2] == 'X')chk[i][j] = 1, c++;
		}
	}
	for (i = 0; i <= n; i++)for (j = 0; j <= m; j++)for (k = 0; k < (1 << (n + 1)); k++)D[i][j][k] = 1e9;
	D[n][0][0] = 0;
	int pj = n, pi = 0;
	for (i = 1; i <= m; i++) {
		for (j = 1; j <= n; j++) {
			Do(D[pj][pi], D[j][i], j, i);
			pi = i;
			pj = j;
		}
	}
	printf("%d\n", (D[n][m][0]+c/2)*2);
}

Compilation message

connect.cpp: In function 'int main()':
connect.cpp:69:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &W, &H);
  ~~~~~^~~~~~~~~~~~~~~~
connect.cpp:70:7: warning: ignoring return value of 'char* fgets(char*, int, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  fgets(p[0], 90, stdin);
  ~~~~~^~~~~~~~~~~~~~~~~
connect.cpp:72:8: warning: ignoring return value of 'char* fgets(char*, int, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   fgets(p[i]+1, 90, stdin);
   ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
80.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 2 ms 504 KB Partially correct (80% score). Wrong board
2 Partially correct 2 ms 504 KB Partially correct (80% score). Wrong board
3 Partially correct 2 ms 760 KB Partially correct (80% score). Wrong board
4 Partially correct 4 ms 1656 KB Partially correct (80% score). Wrong board
5 Partially correct 9 ms 5880 KB Partially correct (80% score). Wrong board
6 Partially correct 3 ms 1272 KB Partially correct (80% score). Wrong board
7 Partially correct 2 ms 888 KB Partially correct (80% score). Wrong board
8 Partially correct 3 ms 1272 KB Partially correct (80% score). Wrong board
9 Partially correct 4 ms 2424 KB Partially correct (80% score). Wrong board
10 Partially correct 5 ms 3192 KB Partially correct (80% score). Wrong board
11 Partially correct 4 ms 2168 KB Partially correct (80% score). Wrong board
12 Partially correct 6 ms 3576 KB Partially correct (80% score). Wrong board
13 Partially correct 6 ms 3832 KB Partially correct (80% score). Wrong board
14 Partially correct 8 ms 5624 KB Partially correct (80% score). Wrong board
15 Partially correct 9 ms 6904 KB Partially correct (80% score). Wrong board
16 Partially correct 12 ms 8952 KB Partially correct (80% score). Wrong board
17 Partially correct 13 ms 9208 KB Partially correct (80% score). Wrong board
18 Partially correct 23 ms 17016 KB Partially correct (80% score). Wrong board
19 Partially correct 27 ms 17016 KB Partially correct (80% score). Wrong board
20 Partially correct 25 ms 17016 KB Partially correct (80% score). Wrong board