oj.uz

Submission #1003076

# Submission time Handle Problem Language Result Execution time Memory
1003076 2024-06-20T05:06:36 Z vjudge1 Robots (APIO13_robots) C++17
60 / 100
 1500 ms 122700 KB 
#include <bits/stdc++.h>
#define speed ios_base::sync_with_stdio(0); cin.tie(0)
#define all(x) x.begin(), x.end()
#define pb push_back
#define x first
#define y second
#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)

using namespace std;

typedef long long ll;

const int maxn = 507;
const int K = 1e5;
const int mod = 1e9 + 7;
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};

int s, n, m;
char a[maxn][maxn];
vector <pair <int, int>> act;
pair <int, int> up[maxn][maxn];
pair <int, int> down[maxn][maxn];
pair <int, int> L[maxn][maxn];
pair <int, int> R[maxn][maxn];
vector <pair <int, int>> g[maxn][maxn];
bool used[maxn][maxn];
bool cycle[maxn][maxn][10];
bool udp[10][10][maxn][maxn];
int dp[10][10][maxn][maxn];

bool correct(pair <int, int> p, int vx, int vy) {
	if (p.x == vx && p.y == vy) return false;
	return true;
}

pair <int, int> build(pair <int, int> v, int k) {
	int vx = v.x, vy = v.y;
	if (a[v.x][v.y] == '.') {
		return v;
	} else if (a[v.x][v.y] == 'A') {
		if (k == 1) {
			if (correct(up[vx][vy], vx, vy)) {
				return build(up[vx][vy], 4);
			}
		} else if (k == 2) {
			if (correct(down[vx][vy], vx, vy)) {
				return build(down[vx][vy], 3);
			} 
		} else if (k == 3) {
			if (correct(R[vx][vy], vx, vy)) {
				return build(R[vx][vy], 1);
			}
		} else {
			if (correct(L[vx][vy], vx, vy)) {
				return build(L[vx][vy], 2);
			}
		}
	} else if (a[v.x][v.y] == 'C') {
		if (k == 1) {
			if (correct(down[vx][vy], vx, vy)) {
				return build(down[vx][vy], 3);
			}
		} else if(k == 2) {
			if (correct(up[vx][vy], vx, vy)) {
				return build(up[vx][vy], 4);
			}
		} else if (k == 3) {
			if (correct(L[vx][vy], vx, vy)) {
				return build(L[vx][vy], 2);
			}
		} else {
			if (correct(R[vx][vy], vx, vy)) {
				return build(R[vx][vy], 1);
			}
		}
	}
	return v;
}

void solve() {
	cin >> s >> m >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> a[i][j];
			if (a[i][j] >= '1' && a[i][j] <= '9') {
				act.pb({i, j});
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		L[i][0] = {i, 1};
		for (int j = 1; j <= m; j++) {
			L[i][j] = L[i][j - 1];
			if (a[i][j - 1] == 'x') L[i][j] = {i, j};
			if (a[i][j - 1] == 'A' || a[i][j - 1] == 'C') L[i][j] = {i, j - 1};
		}
		R[i][m + 1] = {i, m};
		for (int j = m; j >= 1; j--) {
			R[i][j] = R[i][j + 1];
			if (a[i][j + 1] == 'x') R[i][j] = {i, j};
			if (a[i][j + 1] == 'A' || a[i][j + 1] == 'C') R[i][j] = {i, j + 1};
		}
	}
	for (int j = 1; j <= m; j++) {
		up[0][j] = {1, j};
		for (int i = 1; i <= n; i++) {
			up[i][j] = up[i - 1][j];
			if (a[i - 1][j] == 'x') up[i][j] = {i, j};
			if (a[i - 1][j] == 'A' || a[i - 1][j] == 'C') up[i][j] = {i - 1, j};
		}
		down[n + 1][j] = {n, j};
		for (int i = n; i >= 1; i--) {
			down[i][j] = down[i + 1][j];
			if (a[i + 1][j] == 'x') down[i][j] = {i, j};
			if (a[i + 1][j] == 'A' || a[i + 1][j] == 'C') down[i][j] = {i + 1, j};
		}
	}
	for (int rx = 1; rx <= n; rx++) {
		for (int ry = 1; ry <= m; ry++) {
			if (a[rx][ry] == 'x') continue;
			if (correct(up[rx][ry], rx, ry)) g[rx][ry].pb(build(up[rx][ry], 4));
			if (correct(down[rx][ry], rx, ry)) g[rx][ry].pb(build(down[rx][ry], 3));
			if (correct(R[rx][ry], rx, ry)) g[rx][ry].pb(build(R[rx][ry], 1));
			if (correct(L[rx][ry], rx, ry)) g[rx][ry].pb(build(L[rx][ry], 2));
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			for (int l = 1; l <= s; l++) {
				for (int r = 1; r <= s; r++) {
					dp[l][r][i][j] = 1e9;
				}
			}
		}
	}
	for (auto [rx, ry] : act) {
		int i = a[rx][ry] - '0';
		dp[i][i][rx][ry] = 0;
	}
	for (int sz = 1; sz <= s; sz++) {
		for (int l = 1, r = sz; r <= s; l++, r++) {
			set <pair <int, pair <int, int>>> st;
			for (int x = 1; x <= n; x++) {
				for (int y = 1; y <= m; y++) {
					for (int mid = l; mid < r; mid++) {
						dp[l][r][x][y] = min(dp[l][r][x][y], dp[l][mid][x][y] + dp[mid + 1][r][x][y]);
					}
					if (dp[l][r][x][y] != 1e18) st.insert({dp[l][r][x][y], {x, y}});
				}
			}
			while (!st.empty()) {
				pair <int, int> v = st.begin() -> y;
				st.erase(st.begin());
				for (auto [tox, toy] : g[v.x][v.y]) {
					if (dp[l][r][tox][toy] > dp[l][r][v.x][v.y] + 1) {
						st.erase({dp[l][r][tox][toy], {tox, toy}});
						dp[l][r][tox][toy] = dp[l][r][v.x][v.y] + 1;
						st.insert({dp[l][r][tox][toy], {tox, toy}});
					}
				}
			}
		}
	}
	int ans = 1e9;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			ans = min(ans, dp[1][s][i][j]);
		}
	}
	if (ans == 1e9) {
		cout << -1;
		return;
	}
	cout << ans;
}
//1 -> L
//2 -> R
//3 -> up
//4 -> down

/*
4 10 5
1.........
AA...x4...
..A..x....
2....x....
..C.3.A...
*/

const bool cases = 0;

signed main() {
//	speed;
	int test = 1, cnt = 0;
	if (cases) cin >> test;
	while (test--) {
		// cout << "Case " << ++cnt << ": ";
		solve();
	}
}

Compilation message

robots.cpp: In function 'int main()':
robots.cpp:195:16: warning: unused variable 'cnt' [-Wunused-variable]
  195 |  int test = 1, cnt = 0;
      |                ^~~

Subtask #1
10.0 / 10.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6492 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 2 ms 6492 KB Output is correct
4 Correct 2 ms 6748 KB Output is correct
5 Correct 2 ms 6748 KB Output is correct
6 Correct 3 ms 6492 KB Output is correct
7 Correct 3 ms 6492 KB Output is correct
8 Correct 2 ms 6492 KB Output is correct
9 Correct 3 ms 6492 KB Output is correct
10 Correct 3 ms 6748 KB Output is correct
11 Correct 554 ms 66568 KB Output is correct
12 Correct 30 ms 18772 KB Output is correct
13 Correct 381 ms 47912 KB Output is correct
14 Correct 754 ms 66564 KB Output is correct
15 Correct 560 ms 66388 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6492 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 2 ms 6492 KB Output is correct
4 Correct 2 ms 6748 KB Output is correct
5 Correct 2 ms 6748 KB Output is correct
6 Correct 3 ms 6492 KB Output is correct
7 Correct 3 ms 6492 KB Output is correct
8 Correct 2 ms 6492 KB Output is correct
9 Correct 3 ms 6492 KB Output is correct
10 Correct 3 ms 6748 KB Output is correct
11 Correct 554 ms 66568 KB Output is correct
12 Correct 30 ms 18772 KB Output is correct
13 Correct 381 ms 47912 KB Output is correct
14 Correct 754 ms 66564 KB Output is correct
15 Correct 560 ms 66388 KB Output is correct
16 Correct 1478 ms 122700 KB Output is correct
17 Execution timed out 1558 ms 114772 KB Time limit exceeded
18 Halted 0 ms 0 KB -