oj.uz

Submission #136340

# Submission time Handle Problem Language Result Execution time Memory
136340 2019-07-25T07:13:21 Z 윤교준(#3260) Connect (CEOI06_connect) C++14
24 / 100
 236 ms 10568 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<<20];
	fill(dp, dp+(1<<20), 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];
		if(INF <= l) continue;
		l <<= 1;
		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
24.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 6 ms 4472 KB Partially correct (80% score). Wrong board
2 Partially correct 5 ms 4472 KB Partially correct (80% score). Wrong board
3 Runtime error 14 ms 9080 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Partially correct 6 ms 4524 KB Partially correct (80% score). Wrong board
5 Runtime error 14 ms 9296 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 14 ms 9564 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Partially correct 236 ms 4708 KB Partially correct (80% score). Wrong board
8 Partially correct 7 ms 4728 KB Partially correct (80% score). Wrong board
9 Runtime error 14 ms 9596 KB Execution killed with signal 7 (could be triggered by violating memory limits)
10 Runtime error 16 ms 10008 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Partially correct 16 ms 4904 KB Partially correct (80% score). Wrong board
12 Runtime error 17 ms 10020 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 14 ms 9720 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 16 ms 10232 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 13 ms 9948 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 22 ms 10208 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 14 ms 9764 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 20 ms 10568 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 21 ms 10532 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 20 ms 10488 KB Execution killed with signal 11 (could be triggered by violating memory limits)