oj.uz

Submission #136334

# Submission time Handle Problem Language Result Execution time Memory
136334 2019-07-25T07:08:43 Z 윤교준(#3260) Connect (CEOI06_connect) C++14
20 / 100
 13 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];
		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
20.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 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 Partially correct 3 ms 632 KB Partially correct (80% score). Wrong board
5 Runtime error 6 ms 1652 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 5 ms 1764 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 4 ms 1528 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Partially correct 3 ms 892 KB Partially correct (80% score). Wrong board
9 Runtime error 5 ms 1784 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 7 ms 2140 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Partially correct 13 ms 1016 KB Partially correct (80% score). Wrong board
12 Runtime error 9 ms 2296 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 6 ms 2040 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 6 ms 2424 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 4 ms 2040 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 8 ms 2424 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 6 ms 2020 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 11 ms 2808 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 11 ms 2680 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 12 ms 2680 KB Execution killed with signal 11 (could be triggered by violating memory limits)