oj.uz

답안 #384914

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
384914 2021-04-02T16:14:32 Z pure_mem Connect (CEOI06_connect) C++14
64 / 100
 39 ms 28652 KB 
#include <bits/stdc++.h> 
 
#define X first
#define Y second
#define MP make_pair
#define ll long long
 
using namespace std;
 
const int N = 80, INF = 1e9;
const ll mod = 1e9 + 7;
 
int r, c, n, m, dp[12][40][(1 << 12)][2], pr[12][40][(1 << 12)][2], cntX;
string s[N];

void inputs(){
	scanf("%d %d\n", &r, &c);
	for(int i = 0;i < r;i++)
		getline(cin, s[i]), scanf("\n");
	for(int i = 0;i < r;i++)
		for(int j = 0;j < c;j++)
			cntX += (s[i][j] == 'X');
	n = r / 2, m = c / 2;
}

bool good(int x, int y, int tp){
	bool res = 1;
	if(tp <= 4 && s[x][y] != 'X')
		res = 0;
	if(tp == 1 || tp == 9 || tp == 10 || tp == 11){
		if(s[x][y - 1] == '|')
			res = 0;
	}
	if(tp == 2 || tp == 7 || tp == 8 || tp == 11){
		if(s[x - 1][y] == '-')
			res = 0;	
	}
	if(tp == 3 || tp == 6 || tp == 7 || tp == 10){
		if(s[x + 1][y] == '-')
			res = 0;	
	}
	if(tp == 4 || tp == 6 || tp == 8 || tp == 9){
		if(s[x][y + 1] == '|')
			res = 0;
	}
	return res;
}

int main () {
	inputs();
	for(int j = 0;j < m;j++)
		for(int i = 0;i < n;i++)
			for(int mask = 0;mask < (1 << n);mask++)
				dp[i][j][mask][0] = dp[i][j][mask][1] = INF;
	for(int i = 0, j = 0;i < n;i++){
		for(int mask = 0;mask < (1 << n);mask++){
			if(s[i * 2 + 1][j * 2 + 1] == 'X'){
				if(!((mask >> i) & 1)){
					int newmask = mask ^ (1 << i), val = (i ? dp[i - 1][j][mask][1]: INF);
					if(dp[i][j][mask][0] > val && good(i * 2 + 1, j * 2 + 1, 2)){
						dp[i][j][mask][0] = val;
						pr[i][j][mask][0] = 2;
					}
					val = (i ? dp[i - 1][j][mask][0]: INF) + 1;
					if(val > INF && mask == 0)
						val = 1;	
					if(dp[i][j][mask][1] > val && good(i * 2 + 1, j * 2 + 1, 3)){
						dp[i][j][mask][1] = val;
						pr[i][j][mask][1] = 3;
					}
					if(dp[i][j][newmask][0] > val && good(i * 2 + 1, j * 2 + 1, 4)){
						dp[i][j][newmask][0] = val;
						pr[i][j][newmask][0] = 4;
					}	
				}
			}
			else{
				if((mask >> i) & 1)
					continue;
				int val = (i ? dp[i - 1][j][mask][0]: INF);
				if(mask == 0 && i == 0)
					val = 0;
				if(dp[i][j][mask][0] > val && good(i * 2 + 1, j * 2 + 1, 5)){
					dp[i][j][mask][0] = val;
					pr[i][j][mask][0] = 5;
				}
				int newmask = mask ^ (1 << i);
				if(dp[i][j][newmask][1] > val + 3 && good(i * 2 + 1, j * 2 + 1, 6)){
					dp[i][j][newmask][1] = val + 3;
					pr[i][j][newmask][1] = 6;
				}
				val = (i ? dp[i - 1][j][mask][1]: INF);
				if(dp[i][j][mask][1] > val + 2 && good(i * 2 + 1, j * 2 + 1, 7)){
					dp[i][j][mask][1] = val + 2;
					pr[i][j][mask][1] = 7;
				}
				if(dp[i][j][newmask][0] > val + 2 && good(i * 2 + 1, j * 2 + 1, 8)){
					dp[i][j][newmask][0] = val + 2;
					pr[i][j][newmask][0] = 8;
				}
			}
		}	
	}
	for(int j = 1;j < m;j++){
		for(int i = 0;i < n;i++){
			for(int mask = 0;mask < (1 << n);mask++){		
				if(s[i * 2 + 1][j * 2 + 1] == 'X'){
					if(((mask >> i) & 1) && j){
						int newmask = mask ^ (1 << i), val = (i ? dp[i - 1][j][mask][0]: dp[n - 1][j - 1][mask][0]);
						if(dp[i][j][newmask][0] > val && good(i * 2 + 1, j * 2 + 1, 1)){
							dp[i][j][newmask][0] = val;	
							pr[i][j][newmask][0] = 1;
						}
					}
					if(!((mask >> i) & 1)){
						int newmask = mask ^ (1 << i), val = (i ? dp[i - 1][j][mask][1]: INF);
						if(dp[i][j][mask][0] > val && good(i * 2 + 1, j * 2 + 1, 2)){
							dp[i][j][mask][0] = val;
							pr[i][j][mask][0] = 2;
						}
						val = (i ? dp[i - 1][j][mask][0]: dp[n - 1][j - 1][mask][0]) + 1;
						if(dp[i][j][mask][1] > val && good(i * 2 + 1, j * 2 + 1, 3)){
							dp[i][j][mask][1] = val;
							pr[i][j][mask][1] = 3;
						}
						if(dp[i][j][newmask][0] > val && good(i * 2 + 1, j * 2 + 1, 4)){
							dp[i][j][newmask][0] = val;
							pr[i][j][newmask][0] = 4;
						}
					}
				}
				else{
					if((mask >> i) & 1){
						int val = (i ? dp[i - 1][j][mask][0]: dp[n - 1][j - 1][mask][0]);
						if(dp[i][j][mask][0] > val + 2 && good(i * 2 + 1, j * 2 + 1, 9)){
							dp[i][j][mask][0] = val + 2;
							pr[i][j][mask][0] = 9;
						}
						int newmask = mask ^ (1 << i);
						if(dp[i][j][newmask][1] > val + 2 && good(i * 2 + 1, j * 2 + 1, 10)){
							dp[i][j][newmask][1] = val + 2;
							pr[i][j][newmask][1] = 10;
						}
						val = (i ? dp[i - 1][j][mask][1]: INF);
						if(dp[i][j][newmask][0] > val + 1 && good(i * 2 + 1, j * 2 + 1, 11)){
							dp[i][j][newmask][0] = val + 1;
							pr[i][j][newmask][0] = 11;
						}
					}
					else{
						int val = (i ? dp[i - 1][j][mask][0]: dp[n - 1][j - 1][mask][0]);
						if(dp[i][j][mask][0] > val && good(i * 2 + 1, j * 2 + 1, 5)){
							dp[i][j][mask][0] = val;
							pr[i][j][mask][0] = 5;
						}
						int newmask = mask ^ (1 << i);
						if(dp[i][j][newmask][1] > val + 3 && good(i * 2 + 1, j * 2 + 1, 6)){
							dp[i][j][newmask][1] = val + 3;
							pr[i][j][newmask][1] = 6;
						}
						val = (i ? dp[i - 1][j][mask][1]: INF);
						if(dp[i][j][mask][1] > val + 2 && good(i * 2 + 1, j * 2 + 1, 7)){
							dp[i][j][mask][1] = val + 2;
							pr[i][j][mask][1] = 7;
						}
						if(dp[i][j][newmask][0] > val + 2 && good(i * 2 + 1, j * 2 + 1, 8)){
							dp[i][j][newmask][0] = val + 2;
							pr[i][j][newmask][0] = 8;
						}
					}	
				}	
			}
		}	
	}
	printf("%d", dp[n - 1][m - 1][0][0] + cntX / 2);
}

Compilation message

connect.cpp: In function 'void inputs()':
connect.cpp:17:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   17 |  scanf("%d %d\n", &r, &c);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~
connect.cpp:19:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   19 |   getline(cin, s[i]), scanf("\n");
      |                       ~~~~~^~~~~~

Subtask #1
64.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 1 ms 620 KB Partially correct (80% score). Wrong board
2 Partially correct 1 ms 620 KB Partially correct (80% score). Wrong board
3 Partially correct 1 ms 876 KB Partially correct (80% score). Wrong board
4 Incorrect 2 ms 1536 KB Wrong score! (21, expected 28)
5 Partially correct 10 ms 8300 KB Partially correct (80% score). Wrong board
6 Partially correct 3 ms 1900 KB Partially correct (80% score). Wrong board
7 Incorrect 2 ms 1260 KB Wrong score! (69, expected 72)
8 Partially correct 2 ms 1772 KB Partially correct (80% score). Wrong board
9 Partially correct 3 ms 2156 KB Partially correct (80% score). Wrong board
10 Partially correct 3 ms 2796 KB Partially correct (80% score). Wrong board
11 Partially correct 3 ms 2924 KB Partially correct (80% score). Wrong board
12 Partially correct 6 ms 5228 KB Partially correct (80% score). Wrong board
13 Incorrect 7 ms 5612 KB Wrong score! (197, expected 208)
14 Partially correct 7 ms 7276 KB Partially correct (80% score). Wrong board
15 Partially correct 9 ms 8684 KB Partially correct (80% score). Wrong board
16 Partially correct 11 ms 9580 KB Partially correct (80% score). Wrong board
17 Partially correct 12 ms 10604 KB Partially correct (80% score). Wrong board
18 Partially correct 23 ms 20204 KB Partially correct (80% score). Wrong board
19 Partially correct 39 ms 28652 KB Partially correct (80% score). Wrong board
20 Incorrect 27 ms 24044 KB Wrong score! (368, expected 374)