oj.uz

Submission #263386

# Submission time Handle Problem Language Result Execution time Memory
263386 2020-08-13T16:25:42 Z atoiz Robots (APIO13_robots) C++14
100 / 100
 998 ms 51612 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>

using namespace std;

struct MultiList 
{
	using data_t = int;
	static const data_t FAIL = -1;

	vector<pair<int, data_t>> vec;
	bool built;

	void reset()
	{
		built = false;
		vec.clear();
	}

	void add(int val, data_t data)
	{
		vec.emplace_back(-val, data);
	}

	void build()
	{
		sort(vec.begin(), vec.end());
		built = true;
	}

	void normalize()
	{
		if (!built) build();
	}

	data_t get()
	{
		normalize();
		if (vec.empty()) return FAIL;
		return vec.back().second;
	}

	void next()
	{
		normalize();
		if (!vec.empty()) vec.pop_back();
	}
} lis;

const int MAXN = 507, D[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}, INF = 1e8;
int N, R, C, nxt[MAXN][MAXN][4], dist[10][10][MAXN][MAXN];
bool inq[MAXN][MAXN];
string A[MAXN];
int qu[MAXN * MAXN * 4 + 100];

int go(int x, int y, int d)
{
	int &cur = nxt[x][y][d];
	if (~cur) return cur;
	int x0 = x + D[d][0], y0 = y + D[d][1];
	// cout << x << ' ' << y << ' ' << x0 << ' ' << y0 << ' ' << R << ' ' << C << endl;
	if (x0 < 0 || x0 >= R || y0 < 0 || y0 >= C || A[x0][y0] == 'x') return cur = x * C + y;
	if (A[x0][y0] == 'A') d = (d + 3) % 4;
	if (A[x0][y0] == 'C') d = (d + 1) % 4;
	return cur = go(x0, y0, d);
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> N >> C >> R;
	for (int x = 0; x < R; ++x) cin >> A[x];
	memset(nxt, -1, sizeof nxt);
	// cout << go(4, 4, 1) / C << ' ' << go(4, 4, 1) % C << endl;
	// return 0;

	for (int l = 1; l <= N; ++l) for (int r = l; r <= N; ++r) for (int x = 0; x < R; ++x) for (int y = 0; y < C; ++y) {
		dist[l][r][x][y] = INF;
	}
	for (int x = 0; x < R; ++x) for (int y = 0; y < C; ++y) if ('1' <= A[x][y] && A[x][y] <= '9') {
		dist[A[x][y] - '0'][A[x][y] - '0'][x][y] = 0;
	}


	for (int range = 0; range < N; ++range) {
		for (int l = 1; l <= N - range; ++l) {
			lis.reset();
			int r = l + range;

			for (int x = 0; x < R; ++x) for (int y = 0; y < C; ++y) {
				for (int m = l; m < r; ++m) {
					dist[l][r][x][y] = min(dist[l][r][x][y], dist[l][m][x][y] + dist[m + 1][r][x][y]);
				}

				if (dist[l][r][x][y] != INF) {
					lis.add(dist[l][r][x][y], x * C + y);
				}
			}	
			memset(inq, 0, sizeof inq);

			int qi = 0, sz = 0;
			auto upd = [&](int x0, int y0) {
				int d0 = dist[l][r][x0][y0];
				// cout << "upd " << l << ' ' << r << ' ' << x0 << ' ' << y0 << ": " << d0 << endl;
				for (int d = 0; d < 4; ++d) {
					int h1 = go(x0, y0, d), x1 = (h1 / C) % R, y1 = h1 % C;
					int &d1 = dist[l][r][x1][y1];
					if (d1 > d0 + 1) {
						d1 = d0 + 1;
						if (!inq[x1][y1]) {
							inq[x1][y1] = true;
							qu[sz++] = x1 * C + y1;
						}
					}
				}
			};
			while (true) {
				int h2 = lis.get(), x2 = h2 / C, y2 = h2 % C;
				int d2 = (h2 == -1 ? INF : dist[l][r][x2][y2]);

				for (; qi < sz; ++qi) {
					int h0 = qu[qi], x0 = h0 / C, y0 = h0 % C;
					int d0 = dist[l][r][x0][y0];
					if (d0 > d2) break;
					inq[x0][y0] = false;
					upd(x0, y0);
				}

				if (h2 == -1) break;
				lis.next();
				upd(x2, y2);
			}
		}
	}

	int ans = INF;
	for (int x = 0; x < R; ++x) for (int y = 0; y < C; ++y) {
		ans = min(ans, dist[1][N][x][y]);
	}
	if (ans == INF) ans = -1;
	cout << ans << endl;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4608 KB Output is correct
2 Correct 3 ms 4608 KB Output is correct
3 Correct 3 ms 4608 KB Output is correct
4 Correct 3 ms 4736 KB Output is correct
5 Correct 3 ms 4736 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4608 KB Output is correct
2 Correct 3 ms 4608 KB Output is correct
3 Correct 3 ms 4608 KB Output is correct
4 Correct 3 ms 4736 KB Output is correct
5 Correct 3 ms 4736 KB Output is correct
6 Correct 3 ms 4608 KB Output is correct
7 Correct 3 ms 4608 KB Output is correct
8 Correct 3 ms 4608 KB Output is correct
9 Correct 3 ms 4608 KB Output is correct
10 Correct 3 ms 4736 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4608 KB Output is correct
2 Correct 3 ms 4608 KB Output is correct
3 Correct 3 ms 4608 KB Output is correct
4 Correct 3 ms 4736 KB Output is correct
5 Correct 3 ms 4736 KB Output is correct
6 Correct 3 ms 4608 KB Output is correct
7 Correct 3 ms 4608 KB Output is correct
8 Correct 3 ms 4608 KB Output is correct
9 Correct 3 ms 4608 KB Output is correct
10 Correct 3 ms 4736 KB Output is correct
11 Correct 125 ms 32120 KB Output is correct
12 Correct 8 ms 5504 KB Output is correct
13 Correct 27 ms 21632 KB Output is correct
14 Correct 363 ms 32372 KB Output is correct
15 Correct 90 ms 31864 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4608 KB Output is correct
2 Correct 3 ms 4608 KB Output is correct
3 Correct 3 ms 4608 KB Output is correct
4 Correct 3 ms 4736 KB Output is correct
5 Correct 3 ms 4736 KB Output is correct
6 Correct 3 ms 4608 KB Output is correct
7 Correct 3 ms 4608 KB Output is correct
8 Correct 3 ms 4608 KB Output is correct
9 Correct 3 ms 4608 KB Output is correct
10 Correct 3 ms 4736 KB Output is correct
11 Correct 125 ms 32120 KB Output is correct
12 Correct 8 ms 5504 KB Output is correct
13 Correct 27 ms 21632 KB Output is correct
14 Correct 363 ms 32372 KB Output is correct
15 Correct 90 ms 31864 KB Output is correct
16 Correct 86 ms 49980 KB Output is correct
17 Correct 998 ms 51612 KB Output is correct
18 Correct 164 ms 50808 KB Output is correct
19 Correct 92 ms 49968 KB Output is correct
20 Correct 570 ms 51444 KB Output is correct