oj.uz

Submission #46887

# Submission time Handle Problem Language Result Execution time Memory
46887 2018-04-24T14:18:20 Z cheater2k Robots (APIO13_robots) C++17
30 / 100
 721 ms 115192 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 505;
const int INF = 1e9;
const int dx[] = {-1, 0, +1, 0};
const int dy[] = {0, +1, 0, -1};
typedef pair<int,int> ii;

int n, r, c;
char a[N][N];
int dis[N][N][10][10];
bool out[N][N][10][10];
ii dest[N][N][4];

struct state { 
	int dis; int x; int y; int l; int r; 
	bool operator < (const state &other) const {
		return dis > other.dis;
	}
};

bool inside(int x, int y) { return x >= 1 && x <= r && y >= 1 && y <= c; }

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	cin >> n >> c >> r;
	for (int i = 1; i <= r; ++i) {
		for (int j = 1; j <= c; ++j) {
			cin >> a[i][j];
		}
	}
	
	// calculate dest[][][]
	for (int i = 1; i <= r; ++i) {
		for (int j = 1; j <= c; ++j) {
			for (int dir = 0; dir < 4; ++dir) {
				if (dest[i][j][dir] == make_pair(0,0)) { // was not visited
					// dfs using stack
					int destx, desty;
					int x = i, y = j, curdir = dir;
					stack < pair<ii, int> > st; // ((x, y), dir)
					while(true) {
						if (dest[x][y][curdir] != make_pair(0, 0)) {
							destx = dest[x][y][curdir].first;
							desty = dest[x][y][curdir].second;
							break;
						}

						st.push(make_pair(ii(x, y), curdir));
						int ndir = curdir;
						if (a[x][y] == 'A') ndir = (curdir + 3) % 4;
						if (a[x][y] == 'C') ndir = (curdir + 1) % 4;

						int nx = x + dx[ndir], ny = y + dy[ndir];
						if (!inside(nx, ny) || a[nx][ny] == 'x') {
							destx = x; desty = y; break;
						}

						x = nx; y = ny; curdir = ndir;
					}

					while(!st.empty()) {
						x = st.top().first.first, y = st.top().first.second, curdir = st.top().second;
						st.pop();
						dest[x][y][curdir] = {destx, desty};
					}
				}
			}
		}
	}	
	
	// BFS
	priority_queue <state> q;
	for (int i = 1; i <= r; ++i) for (int j = 1; j <= c; ++j) {
		for (int l = 1; l <= n; ++l) for (int r = 1; r <= n; ++r) {
			dis[i][j][l][r] = INF;
		}
	}
	for (int i = 1; i <= r; ++i) for (int j = 1; j <= c; ++j) {
		if (a[i][j] >= '1' && a[i][j] <= '9') {
			dis[i][j][a[i][j] - '0'][a[i][j] - '0'] = 0;
			q.push({0, i, j, a[i][j] - '0', a[i][j] - '0'});
		}
	}

	while(!q.empty()) {
		auto t = q.top(); q.pop();
		int x = t.x, y = t.y, l = t.l, r = t.r;
		if (l == 1 && r == n) {
			printf("%d\n", dis[x][y][l][r]); return 0;
		}
		if (t.dis != dis[x][y][l][r]) continue;
		out[x][y][l][r] = true;
		
		//cerr << x << ' ' << y << "[" << l << ' ' << r << "] -> " << dis[x][y][l][r] << endl;

		// push
		for (int dir = 0; dir < 4; ++dir) {
			int nx = dest[x][y][dir].first, ny = dest[x][y][dir].second;
			if (dis[nx][ny][l][r] > dis[x][y][l][r] + 1) {
				dis[nx][ny][l][r] = dis[x][y][l][r] + 1;
				q.push({dis[nx][ny][l][r], nx, ny, l, r});
			};
		}

		// merge
		for (int k = 1; k <= l - 1; ++k) if (out[x][y][k][l - 1]) {
			if (dis[x][y][k][r] > dis[x][y][l][r] + dis[x][y][k][l - 1]) {
				dis[x][y][k][r] = dis[x][y][l][r] + dis[x][y][k][l - 1];
				q.push({dis[x][y][k][r], x, y, k, r});
			}
		}
		for (int k = r + 1; k <= n; ++k) if (out[x][y][r + 1][k]) {
			if (dis[x][y][l][k] > dis[x][y][l][r] + dis[x][y][r + 1][k]) {
				dis[x][y][l][k] = dis[x][y][l][r] + dis[x][y][r + 1][k];
				q.push({dis[x][y][l][k], x, y, l, k});
			}
		}
	}
	
	printf("-1\n");
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 2 ms 492 KB Output is correct
4 Correct 2 ms 612 KB Output is correct
5 Correct 2 ms 612 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 2 ms 492 KB Output is correct
4 Correct 2 ms 612 KB Output is correct
5 Correct 2 ms 612 KB Output is correct
6 Correct 2 ms 612 KB Output is correct
7 Correct 2 ms 612 KB Output is correct
8 Correct 2 ms 612 KB Output is correct
9 Correct 2 ms 612 KB Output is correct
10 Correct 2 ms 692 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 2 ms 492 KB Output is correct
4 Correct 2 ms 612 KB Output is correct
5 Correct 2 ms 612 KB Output is correct
6 Correct 2 ms 612 KB Output is correct
7 Correct 2 ms 612 KB Output is correct
8 Correct 2 ms 612 KB Output is correct
9 Correct 2 ms 612 KB Output is correct
10 Correct 2 ms 692 KB Output is correct
11 Correct 462 ms 52000 KB Output is correct
12 Correct 80 ms 52000 KB Output is correct
13 Correct 96 ms 52000 KB Output is correct
14 Runtime error 721 ms 115192 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 2 ms 492 KB Output is correct
4 Correct 2 ms 612 KB Output is correct
5 Correct 2 ms 612 KB Output is correct
6 Correct 2 ms 612 KB Output is correct
7 Correct 2 ms 612 KB Output is correct
8 Correct 2 ms 612 KB Output is correct
9 Correct 2 ms 612 KB Output is correct
10 Correct 2 ms 692 KB Output is correct
11 Correct 462 ms 52000 KB Output is correct
12 Correct 80 ms 52000 KB Output is correct
13 Correct 96 ms 52000 KB Output is correct
14 Runtime error 721 ms 115192 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Halted 0 ms 0 KB -