oj.uz

Submission #490736

# Submission time Handle Problem Language Result Execution time Memory
490736 2021-11-29T02:51:11 Z atoiz Robots (APIO13_robots) C++14
100 / 100
 682 ms 63612 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;
	static const int MAX_VAL = 500 * 500 * 10 + 1000, MAX_NODES = 500 * 500 * 10 + 1000;
 
	int start[MAX_VAL];
	struct node { int nxt; data_t data; } a[MAX_NODES];
 
	int cntNodes, maxVal, curVal, curNode;
 
	void reset()
	{
		memset(start, 0, sizeof start);
		cntNodes = 0, maxVal = 0, curVal = -1, curNode = 0;
	}
 
	void add(int val, data_t data)
	{
		a[++cntNodes] = {start[val], data};
		start[val] = cntNodes;
		maxVal = max(maxVal, val);
	}
 
	void normalize()
	{
		if (curNode == 0) {
			for (++curVal; curVal <= maxVal && !start[curVal]; ++curVal);
			if (curVal <= maxVal) curNode = start[curVal];
		}
	}	
 
	data_t get()
	{
		normalize();
		if (curVal > maxVal) return FAIL;
		data_t data = a[curNode].data;
		return data;
	}
 
	void next()
	{
		normalize();
		if (curVal <= maxVal) curNode = a[curNode].nxt;
	}
} 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], vis[MAXN][MAXN][10];
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;
    if (vis[x][y][d]) return cur;
    vis[x][y][d] = true;
	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) {
			int r = l + range;
		  //  cout << l << ' ' << r << endl;
 
			lis.reset();
			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);
					if (h1 == -1) continue;
					int 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;
				    // cout << "s" << endl;
					upd(x0, y0);
				    // cout << "t" << endl;
				}
 
				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 9 ms 14412 KB Output is correct
2 Correct 9 ms 14368 KB Output is correct
3 Correct 8 ms 14380 KB Output is correct
4 Correct 10 ms 14452 KB Output is correct
5 Correct 8 ms 14412 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14412 KB Output is correct
2 Correct 9 ms 14368 KB Output is correct
3 Correct 8 ms 14380 KB Output is correct
4 Correct 10 ms 14452 KB Output is correct
5 Correct 8 ms 14412 KB Output is correct
6 Correct 8 ms 14440 KB Output is correct
7 Correct 9 ms 14436 KB Output is correct
8 Correct 9 ms 14412 KB Output is correct
9 Correct 10 ms 14440 KB Output is correct
10 Correct 9 ms 14400 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14412 KB Output is correct
2 Correct 9 ms 14368 KB Output is correct
3 Correct 8 ms 14380 KB Output is correct
4 Correct 10 ms 14452 KB Output is correct
5 Correct 8 ms 14412 KB Output is correct
6 Correct 8 ms 14440 KB Output is correct
7 Correct 9 ms 14436 KB Output is correct
8 Correct 9 ms 14412 KB Output is correct
9 Correct 10 ms 14440 KB Output is correct
10 Correct 9 ms 14400 KB Output is correct
11 Correct 131 ms 43112 KB Output is correct
12 Correct 12 ms 16708 KB Output is correct
13 Correct 57 ms 32852 KB Output is correct
14 Correct 286 ms 43300 KB Output is correct
15 Correct 112 ms 42916 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14412 KB Output is correct
2 Correct 9 ms 14368 KB Output is correct
3 Correct 8 ms 14380 KB Output is correct
4 Correct 10 ms 14452 KB Output is correct
5 Correct 8 ms 14412 KB Output is correct
6 Correct 8 ms 14440 KB Output is correct
7 Correct 9 ms 14436 KB Output is correct
8 Correct 9 ms 14412 KB Output is correct
9 Correct 10 ms 14440 KB Output is correct
10 Correct 9 ms 14400 KB Output is correct
11 Correct 131 ms 43112 KB Output is correct
12 Correct 12 ms 16708 KB Output is correct
13 Correct 57 ms 32852 KB Output is correct
14 Correct 286 ms 43300 KB Output is correct
15 Correct 112 ms 42916 KB Output is correct
16 Correct 110 ms 62260 KB Output is correct
17 Correct 682 ms 63612 KB Output is correct
18 Correct 165 ms 62784 KB Output is correct
19 Correct 115 ms 62380 KB Output is correct
20 Correct 406 ms 63032 KB Output is correct