oj.uz

Submission #136331

# Submission time Handle Problem Language Result Execution time Memory
136331 2019-07-25T07:07:18 Z 윤교준(#3260) Connect (CEOI06_connect) C++14
16 / 100
 14 ms 2808 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 int dx[] = { 0, 1, 0, -1 }, dy[] = { -1, 0, 1, 0 };

int C[12][39][12][39];
vector<pii> XV;

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];
		if(isX[i][j]) XV.eb(i, j);
	}
	for(int i = 0; i < H; i++) for(int j = 0; j < W; j++) {
		fill(C[i][j][0], C[i][j][11]+39, INF);
		queue<int> PQ;
		C[i][j][i][j] = 0;
		PQ.push(i<<10|j);
		for(int key, y, x, dst; !PQ.empty();) {
			key = PQ.front(); PQ.pop();
			y = key >> 10; x = key & ((1<<10)-1);
			dst = C[i][j][y][x] + 1;
			for(int dr = 0, ny, nx; dr < 4; dr++) if(B[y][x][dr]) {
				ny = y+dy[dr]; nx = x+dx[dr];
				if(C[i][j][ny][nx] <= dst) continue;
				C[i][j][ny][nx] = dst;
				PQ.push(ny<<10|nx);
			}
		}
	}

	int dp[1<<16];
	fill(dp, dp+(1<<16), INF);
	dp[0] = 0;
	int n = sz(XV);
	for(int i = 0; i < n; i++) for(int j = i+1; j < n; j++) {
		int l = C[XV[i].first][XV[i].second][XV[j].first][XV[j].second];
		l = l * 2;
		for(int key = 1<<n; key--;) if(!(key & (1<<i | 1<<j))) {
			upmin(dp[key | 1<<i | 1<<j], dp[key] + l);
		}
	}
	Ans = dp[(1<<n)-1];

	cout << Ans << endl;
	return 0;
}

Compilation message

connect.cpp: In function 'int main()':
connect.cpp:23: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:24: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
16.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 3 ms 632 KB Partially correct (80% score). Wrong board
2 Partially correct 3 ms 632 KB Partially correct (80% score). Wrong board
3 Runtime error 4 ms 1272 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Incorrect 3 ms 632 KB Wrong score! (-1111638595, expected 28)
5 Runtime error 6 ms 1528 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 6 ms 1656 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 5 ms 1528 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Partially correct 4 ms 1016 KB Partially correct (80% score). Wrong board
9 Runtime error 5 ms 1912 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 7 ms 2168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Partially correct 14 ms 1016 KB Partially correct (80% score). Wrong board
12 Runtime error 10 ms 2296 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 6 ms 2076 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 7 ms 2396 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 5 ms 2040 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 8 ms 2552 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 5 ms 1912 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 12 ms 2680 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 12 ms 2808 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 13 ms 2808 KB Execution killed with signal 11 (could be triggered by violating memory limits)