oj.uz

Submission #465955

# Submission time Handle Problem Language Result Execution time Memory
465955 2021-08-17T12:27:40 Z nonsensenonsense1 Robots (APIO13_robots) C++17
100 / 100
 1006 ms 110040 KB 
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#include <utility>

const int INF = 0x3f3f3f3f;

int move[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

inline void mnm(int &a, int b) 
{
	if (a > b) a = b;
}

const int N = 500;
const int M = 10;
int n, h, w;
std::pair<int, int> to[N][N][4];
int dist[M][M][N][N];
bool u[N][N];
char s[N][N + 1];

inline bool out(int x, int y) 
{
	return x >= h || x < 0 || y >= w || y < 0 || s[x][y] == 'x';
}

std::pair<int, int> to_f(int x, int y, int dir) 
{
	if (to[x][y][dir].second != -1) return to[x][y][dir];
	to[x][y][dir].second = 0;
	int dir_ = dir;
	if (s[x][y] == 'C') ++dir;
	else if (s[x][y] == 'A') --dir;
	if (dir == 4) dir = 0;
	if (dir == -1) dir = 3;
	if (out(x + move[dir][0], y + move[dir][1])) to[x][y][dir_] = std::make_pair(x, y);
	else to[x][y][dir_] = to_f(x + move[dir][0], y + move[dir][1], dir);
	return to[x][y][dir_];
}

int main() 
{
	memset(dist, 0x3f, N * N * M * M << 2);
	scanf("%d%d%d", &n, &w, &h);
	for (int i = 0; i < h; ++i) {
		scanf("%s", s[i]);
		for (int j = 0; j < w; ++j) {
			if (s[i][j] >= '1' && s[i][j] <= '9') dist[s[i][j] - '1'][s[i][j] - '1'][i][j] = 0;
			for (int k = 0; k < 4; ++k) to[i][j][k] = std::make_pair(-1, -1);
		}
	}
	for (int d = 0; d < n; ++d) for (int l = 0; l < n - d; ++l) {
		int r = l + d;
		std::vector<std::pair<int, std::pair<int, int> > > pos;
		int (*ptr)[N] = dist[l][r];
		for (int i = 0; i < h; ++i) for (int j = 0; j < w; ++j) if (ptr[i][j] != INF) pos.push_back(std::make_pair(ptr[i][j], std::make_pair(i, j)));
		std::sort(pos.begin(), pos.end());
		if (d == n - 1 && !pos.empty()) {
			printf("%d\n", pos.front().first);
			return 0;
		}
		std::queue<std::pair<int, int> > q;
		memset(u, 0, N * N);
		for (int i = 0; i < (int)pos.size() || !q.empty();) {
			int x, y;
			if (q.empty() || i < (int)pos.size() && pos[i].first <= ptr[q.front().first][q.front().second]) {
				x = pos[i].second.first;
				y = pos[i].second.second;
				++i;
			}
			else {
				x = q.front().first;
				y = q.front().second;
				q.pop();
			}
			if (!u[x][y]) {
				u[x][y] = true;
				for (int j = 0; j < l; ++j) mnm(dist[j][r][x][y], dist[j][l - 1][x][y] + ptr[x][y]);
				for (int j = r + 1; j < n; ++j) mnm(dist[l][j][x][y], dist[r + 1][j][x][y] + ptr[x][y]);
				for (int j = 0; j < 4; ++j) {
					std::pair<int, int> next = to_f(x, y, j);
					if (next.second != -1) {
						mnm(ptr[next.first][next.second], ptr[x][y] + 1);
						q.push(next);
					}
				}
			}
		}
	}
	printf("-1\n");
	return 0;
}

Compilation message

robots.cpp: In function 'int main()':
robots.cpp:68:41: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   68 |    if (q.empty() || i < (int)pos.size() && pos[i].first <= ptr[q.front().first][q.front().second]) {
      |                     ~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
robots.cpp:46:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |  scanf("%d%d%d", &n, &w, &h);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
robots.cpp:48:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |   scanf("%s", s[i]);
      |   ~~~~~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 98356 KB Output is correct
2 Correct 41 ms 98256 KB Output is correct
3 Correct 43 ms 98276 KB Output is correct
4 Correct 42 ms 98308 KB Output is correct
5 Correct 41 ms 98300 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 98356 KB Output is correct
2 Correct 41 ms 98256 KB Output is correct
3 Correct 43 ms 98276 KB Output is correct
4 Correct 42 ms 98308 KB Output is correct
5 Correct 41 ms 98300 KB Output is correct
6 Correct 40 ms 98376 KB Output is correct
7 Correct 40 ms 98336 KB Output is correct
8 Correct 42 ms 98320 KB Output is correct
9 Correct 41 ms 98276 KB Output is correct
10 Correct 42 ms 98372 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 98356 KB Output is correct
2 Correct 41 ms 98256 KB Output is correct
3 Correct 43 ms 98276 KB Output is correct
4 Correct 42 ms 98308 KB Output is correct
5 Correct 41 ms 98300 KB Output is correct
6 Correct 40 ms 98376 KB Output is correct
7 Correct 40 ms 98336 KB Output is correct
8 Correct 42 ms 98320 KB Output is correct
9 Correct 41 ms 98276 KB Output is correct
10 Correct 42 ms 98372 KB Output is correct
11 Correct 154 ms 103328 KB Output is correct
12 Correct 46 ms 102200 KB Output is correct
13 Correct 52 ms 102524 KB Output is correct
14 Correct 373 ms 103792 KB Output is correct
15 Correct 91 ms 103084 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 98356 KB Output is correct
2 Correct 41 ms 98256 KB Output is correct
3 Correct 43 ms 98276 KB Output is correct
4 Correct 42 ms 98308 KB Output is correct
5 Correct 41 ms 98300 KB Output is correct
6 Correct 40 ms 98376 KB Output is correct
7 Correct 40 ms 98336 KB Output is correct
8 Correct 42 ms 98320 KB Output is correct
9 Correct 41 ms 98276 KB Output is correct
10 Correct 42 ms 98372 KB Output is correct
11 Correct 154 ms 103328 KB Output is correct
12 Correct 46 ms 102200 KB Output is correct
13 Correct 52 ms 102524 KB Output is correct
14 Correct 373 ms 103792 KB Output is correct
15 Correct 91 ms 103084 KB Output is correct
16 Correct 69 ms 106640 KB Output is correct
17 Correct 1006 ms 110040 KB Output is correct
18 Correct 167 ms 108696 KB Output is correct
19 Correct 91 ms 106708 KB Output is correct
20 Correct 609 ms 109812 KB Output is correct