oj.uz

Submission #136327

# Submission time Handle Problem Language Result Execution time Memory
136327 2019-07-25T07:04:36 Z 윤교준(#3260) Connect (CEOI06_connect) C++14
0 / 100
 10 ms 1144 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);
			}
		}
	}

	bitset<5555> chk;
	for(int i = 0, n = sz(XV); i < n; i++) if(!chk[i]) {
		int mn = INF, mni = -1;
		for(int j = 0; j < n; j++) if(j != i && !chk[j]) {
			int t = C[XV[i].first][XV[i].second][XV[j].first][XV[j].second];
			if(mn <= t) continue;
			mn = t; mni = j;
		}
		chk[i] = chk[mni] = true;
		Ans += mn * 2 - 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
0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Wrong score! (27, expected 26)
2 Incorrect 2 ms 348 KB Wrong score! (44, expected 40)
3 Incorrect 2 ms 504 KB Wrong score! (118, expected 74)
4 Incorrect 2 ms 376 KB Wrong score! (22, expected 28)
5 Incorrect 3 ms 632 KB Wrong score! (82, expected 102)
6 Incorrect 3 ms 632 KB Wrong score! (145, expected 112)
7 Incorrect 3 ms 504 KB Wrong score! (94, expected 72)
8 Incorrect 3 ms 760 KB Wrong score! (129, expected 94)
9 Incorrect 4 ms 760 KB Wrong score! (129, expected 132)
10 Incorrect 5 ms 888 KB Wrong score! (173, expected 208)
11 Incorrect 3 ms 764 KB Wrong score! (150, expected 106)
12 Incorrect 6 ms 1016 KB Wrong score! (240, expected 268)
13 Incorrect 4 ms 888 KB Wrong score! (159, expected 208)
14 Incorrect 3 ms 1016 KB Wrong score! (502, expected 462)
15 Incorrect 3 ms 888 KB Wrong score! (447, expected 422)
16 Incorrect 6 ms 1016 KB Wrong score! (695, expected 664)
17 Incorrect 4 ms 760 KB Wrong score! (331, expected 288)
18 Incorrect 10 ms 1144 KB Wrong score! (337, expected 296)
19 Incorrect 9 ms 1144 KB Wrong score! (195, expected 212)
20 Incorrect 10 ms 1144 KB Wrong score! (316, expected 374)