oj.uz

Submission #136462

# Submission time Handle Problem Language Result Execution time Memory
136462 2019-07-25T10:38:47 Z sebinkim Connect (CEOI06_connect) C++14
16 / 100
 500 ms 65536 KB 
#include <bits/stdc++.h>

using namespace std;

int D[3030][5050];
char S[33][99];
int n, m;

int main()
{
	int i, j, x, y, t;
	
	scanf("%d%d\n", &n, &m);
	
	for(i=0; i<n; i++){
		fgets(S[i], 88, stdin);
	}
	
	n /= 2; m /= 2;
	
	for(i=0; i<=n*m; i++){
		for(j=0; j<(1<<m+1); j++){
			D[i][j] = 1e9;
		}
	}
	
	D[0][0] = 0;
	
	for(i=0; i<n*m; i++){
		x = i / m << 1 | 1; y = i % m << 1 | 1;
		for(j=0; j<(1<<m+1); j++){
			if(S[x][y] == 'X'){
				if((j & 3) == 3) continue;
				else if(j & 3){
					t = j >> 1 & ~1;
					D[i + 1][t] = min(D[i + 1][t], D[i][j] + 1);
				}
				else{
					if(S[x][y + 1] != '|'){
						t = j >> 1 | 1;
						D[i + 1][t] = min(D[i + 1][t], D[i][j] + 1);
					}
					if(S[x + 1][y] != '-'){
						t = j >> 1 & ~1 | 1 << m;
						D[i + 1][t] = min(D[i + 1][t], D[i][j] + 1);
					}
				}
			}
			else{
				if((j & 3) == 3){
					t = j >> 1 & ~1;
					D[i + 1][t] = min(D[i + 1][t], D[i][j] + 2);
				}
				else if(j & 3){
					if(S[x][y + 1] != '|'){
						t = j >> 1 | 1;
						D[i + 1][t] = min(D[i + 1][t], D[i][j] + 2);
					}
					if(S[x + 1][y] != '-'){
						t = j >> 1 & ~1 | 1 << m;
						D[i + 1][t] = min(D[i + 1][t], D[i][j] + 2);
					}
				}
				else{
					t = j >> 1 & ~1;
					D[i + 1][t] = min(D[i + 1][t], D[i][j]);
					if(S[x][y + 1] != '|' && S[x + 1][y] != '-'){
						t = j >> 1 | 1 | 1 << m;
						D[i + 1][t] = min(D[i + 1][t], D[i][j] + 2);
					}
				}
			}
		}
	}
	
	printf("%d\n", D[n * m][0]);
	
	return 0;
}

Compilation message

connect.cpp: In function 'int main()':
connect.cpp:22:19: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   for(j=0; j<(1<<m+1); j++){
                  ~^~
connect.cpp:31:19: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   for(j=0; j<(1<<m+1); j++){
                  ~^~
connect.cpp:44:18: warning: suggest parentheses around arithmetic in operand of '|' [-Wparentheses]
       t = j >> 1 & ~1 | 1 << m;
           ~~~~~~~^~~~
connect.cpp:60:18: warning: suggest parentheses around arithmetic in operand of '|' [-Wparentheses]
       t = j >> 1 & ~1 | 1 << m;
           ~~~~~~~^~~~
connect.cpp:13:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d\n", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~~~
connect.cpp:16:8: warning: ignoring return value of 'char* fgets(char*, int, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   fgets(S[i], 88, stdin);
   ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
16.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 2 ms 632 KB Partially correct (80% score). Wrong board
2 Partially correct 2 ms 504 KB Partially correct (80% score). Wrong board
3 Partially correct 3 ms 1144 KB Partially correct (80% score). Wrong board
4 Partially correct 2 ms 376 KB Partially correct (80% score). Wrong board
5 Incorrect 9 ms 3192 KB Wrong score! (74, expected 102)
6 Incorrect 3 ms 1272 KB Wrong score! (1000000000, expected 112)
7 Incorrect 66 ms 3064 KB Wrong score! (8, expected 72)
8 Runtime error 150 ms 65536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 151 ms 65536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Incorrect 3 ms 1784 KB Wrong score! (1000000000, expected 208)
11 Execution timed out 1048 ms 36732 KB Time limit exceeded
12 Incorrect 4 ms 2044 KB Wrong score! (1000000000, expected 268)
13 Runtime error 149 ms 65536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Incorrect 3 ms 2296 KB Wrong score! (1000000000, expected 462)
15 Runtime error 152 ms 65536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Incorrect 3 ms 1912 KB Wrong score! (1000000000, expected 664)
17 Execution timed out 1080 ms 13288 KB Time limit exceeded
18 Incorrect 4 ms 2680 KB Wrong score! (1000000000, expected 296)
19 Incorrect 4 ms 2680 KB Wrong score! (224, expected 212)
20 Incorrect 4 ms 2680 KB Wrong score! (1000000000, expected 374)