oj.uz

Submission #552405

# Submission time Handle Problem Language Result Execution time Memory
552405 2022-04-23T06:08:38 Z QwertyPi Robots (APIO13_robots) C++14
60 / 100
 680 ms 163840 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
using namespace std;
typedef pair<int, int> pii;
const int MAXN = 501, MAXM = 501, MAXD = 9;
const int INF = (1 << 25);
char board[MAXN][MAXM];
int dp[MAXN][MAXM][MAXD][MAXD];
int dd[MAXN][MAXM];
pii f[MAXN][MAXM][4];
pii pos[MAXD];
 
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, -1, 0, 1};
 
int d, n, m;
bool in(int i, int j){
	return 0 <= i && i < n && 0 <= j && j < m && board[i][j] != 'x';
}
 
bool vis[MAXN][MAXM][4];
inline pii dfs(int i, int j, int dir){
	if(vis[i][j][dir]) return {-1, -1};
	if(f[i][j][dir].fi != -2) return f[i][j][dir];
	vis[i][j][dir] = true;
	if(!in(i + dx[dir], j + dy[dir])){
		f[i][j][dir] = {i, j};
		vis[i][j][dir] = false;
		return {i, j};
	}
	f[i][j][dir] = dfs(i + dx[dir], j + dy[dir], (dir + dd[i + dx[dir]][j + dy[dir]] + 4) % 4);
	vis[i][j][dir] = false;
	return f[i][j][dir];
}
 
struct CMP{
	bool operator()(pair<pii, pii> a, pair<pii, pii> b){
		return a.fi.fi > b.fi.fi;
	}
};
 
vector<pair<pii, pii>> q[MAXN * MAXM];
int main(){
	cin >> d >> m >> n;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			cin >> board[i][j];
			if(board[i][j] >= '0' && board[i][j] <= '9') pos[board[i][j] - '1'] = {i, j}, board[i][j] = '.';
			if(board[i][j] == 'C') dd[i][j] = 1;
			if(board[i][j] == 'A') dd[i][j] = -1;
		}
	}
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			for(int dir = 0; dir < 4; dir++){
				f[i][j][dir].fi = -2;
			}
		}
	}
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			for(int dir = 0; dir < 4; dir++){
				if(f[i][j][dir].fi == -2) dfs(i, j, dir);
			}
		}
	}
//	for(int i = 0; i < n; i++){
//		for(int j = 0; j < m; j++){
//			for(int k = 0; k < 4; k++){
//				cout << i << ' ' << j << ' ' << k << ' ' << f[i][j][k].fi << ' ' << f[i][j][k].se << endl;
//			}
//		}
//	}
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			for(int d1 = 0; d1 < d; d1++){
				for(int d2 = d1; d2 < d; d2++){
					dp[i][j][d1][d2] = INF;
				}
			}
		}
	}

	for(int i = 0; i < d; i++){
		for(int j = i; j >= 1; j--){
			int c = dp[pos[i].fi][pos[i].se][j - 1][i - 1];
			if(c >= INF) continue;
			q[c].push_back({{c, j - 1}, pos[i]});
			dp[pos[i].fi][pos[i].se][j - 1][i] = c;
		}
		q[0].push_back({{0, i}, pos[i]});
		dp[pos[i].fi][pos[i].se][i][i] = 0;
		for(int k = 0; k <= n * m; k++){
			while(!q[k].empty()){
				pair<pii, pii> v = q[k].back(); q[k].pop_back();
				int cost = v.fi.fi, nd = v.fi.se, x = v.se.fi, y = v.se.se;
				for(int dir = 0; dir < 4; dir++){
					int nx = f[x][y][dir].fi, ny = f[x][y][dir].se;
					if(nx == x && ny == y) continue;
					int co = cost + 1;
					if(co >= dp[nx][ny][nd][i]) continue;
					dp[nx][ny][nd][i] = co;
					q[co].push_back({{co, nd}, {nx, ny}});
					for(int j = nd; j >= 1; j--){
						if(co + dp[nx][ny][j - 1][nd - 1] >= dp[nx][ny][j - 1][i]) continue;
						dp[nx][ny][j - 1][i] = co + dp[nx][ny][j - 1][nd - 1];
						q[co + dp[nx][ny][j - 1][nd - 1]].push_back({{co + dp[nx][ny][j - 1][nd - 1], j - 1}, {nx, ny}});
					}
				}
			}
		}
	}
	
	int ans = INF;
//	for(int d1 = 0; d1 < d; d1++){
//		for(int d2 = d1; d2 < d; d2++){
//			cout << "d " << d1 << ' ' << d2 << endl;
//			for(int i = 0; i < n; i++){
//				for(int j = 0; j < m; j++){
//					cout << (dp[i][j][d1][d2] >= INF ? -1 : dp[i][j][d1][d2]) << ' ';
//				}
//				cout << endl;
//			}
//		}
//	}
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			ans = min(ans, dp[i][j][0][d - 1]);
		}
	}
	cout << (ans >= INF ? -1 : ans) << endl;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6100 KB Output is correct
2 Correct 3 ms 6100 KB Output is correct
3 Correct 3 ms 6100 KB Output is correct
4 Correct 3 ms 6356 KB Output is correct
5 Correct 3 ms 6356 KB Output is correct
6 Correct 3 ms 6228 KB Output is correct
7 Correct 3 ms 6228 KB Output is correct
8 Correct 3 ms 6228 KB Output is correct
9 Correct 3 ms 6228 KB Output is correct
10 Correct 3 ms 6356 KB Output is correct
11 Correct 114 ms 50168 KB Output is correct
12 Correct 31 ms 40776 KB Output is correct
13 Correct 31 ms 40840 KB Output is correct
14 Correct 392 ms 75304 KB Output is correct
15 Correct 69 ms 44028 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6100 KB Output is correct
2 Correct 3 ms 6100 KB Output is correct
3 Correct 3 ms 6100 KB Output is correct
4 Correct 3 ms 6356 KB Output is correct
5 Correct 3 ms 6356 KB Output is correct
6 Correct 3 ms 6228 KB Output is correct
7 Correct 3 ms 6228 KB Output is correct
8 Correct 3 ms 6228 KB Output is correct
9 Correct 3 ms 6228 KB Output is correct
10 Correct 3 ms 6356 KB Output is correct
11 Correct 114 ms 50168 KB Output is correct
12 Correct 31 ms 40776 KB Output is correct
13 Correct 31 ms 40840 KB Output is correct
14 Correct 392 ms 75304 KB Output is correct
15 Correct 69 ms 44028 KB Output is correct
16 Correct 92 ms 95076 KB Output is correct
17 Runtime error 680 ms 163840 KB Execution killed with signal 9
18 Halted 0 ms 0 KB -