oj.uz

Submission #500709

# Submission time Handle Problem Language Result Execution time Memory
500709 2021-12-31T21:01:08 Z CodeTiger927 Robots (APIO13_robots) C++14
100 / 100
 434 ms 134180 KB 
using namespace std;

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>

#define MAXN 505
#define INF 1e6

int N,M,K,dp[9][9][MAXN][MAXN],mxn;
vector<pair<int,int>> dist[MAXN * MAXN];
pair<int,int> to[MAXN][MAXN][4];
char g[MAXN][MAXN];
bool vis[MAXN][MAXN],vis2[MAXN][MAXN];
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};
vector<pair<pair<int,int>,int>> order;

pair<int,int> dfs(int a,int b,int c) {
	if(to[a][b][c].first != 0) return to[a][b][c];
	to[a][b][c] = {a,b};
	if(a <= 0 || a > N || b <= 0 || b > M || g[a][b] == 'x') {
		return to[a][b][c] = {-1,-1};
	}else if(g[a][b] == '.') {
		to[a][b][c] = dfs(a + dx[c],b + dy[c],c);
	}else if(g[a][b] == 'C') {
		int uwu = (c + 1) % 4;
		to[a][b][c] = dfs(a + dx[uwu],b + dy[uwu],uwu);
	}else{
		int uwu = (c + 3) % 4;
		to[a][b][c] = dfs(a + dx[uwu],b + dy[uwu],uwu);
	}
	if(to[a][b][c].first == -1) to[a][b][c] = {a,b};
	order.push_back({{a,b},c});
	return to[a][b][c];
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> K >> M >> N;
	memset(dp,-1,sizeof(dp));
	for(int i = 1;i <= N;++i) {
		for(int j = 1;j <= M;++j) {
			cin >> g[i][j];
			if(g[i][j] - '1' < K && g[i][j] - '1' >= 0) {
				int uwu = g[i][j] - '1';
				dp[uwu][uwu][i][j] = 0;
				// cout << uwu << " " << i << " " << j << endl;
				g[i][j] = '.';
				vis[i][j] = true;
			}
		}
	}
	for(int i = 1;i <= N;++i) {
		for(int j = 1;j <= M;++j) {
			for(int k = 0;k < 4;++k) {
				dfs(i,j,k);
			}
		}
	}
	reverse(order.begin(),order.end());
	for(int k = 0;k < K;++k) {
		for(int i = 0;i < K - k;++i) {
			// cout << dp[0][1][1][1] << endl;
			int j = i + k;
			// cout << i << " " << j << endl;
			mxn = 0;
			for(int a = 1;a <= N;++a) {
				for(int b = 1;b <= M;++b) {
					// cout << a << " " << b << endl;
					if(dp[i][j][a][b] == -1) dp[i][j][a][b] = INF;
					if(g[a][b] == 'x' || !vis[a][b]) continue;
					for(int l = i;l < j;++l) {
						dp[i][j][a][b] = min(dp[i][j][a][b],dp[i][l][a][b] + dp[l + 1][j][a][b]);
					}
					if(dp[i][j][a][b] < INF) {
						dist[dp[i][j][a][b]].push_back({a,b});
						mxn = max(mxn,dp[i][j][a][b]);
					}
					// if(dp[i][j][a][b] < INF) cout << dp[i][j][a][b] << endl;
				}
			}
			// cout << "DONE" << endl;
			memset(vis2,0,sizeof(vis2));
			for(int a = 0;a <= mxn;++a) {
				// cout << a << " " << mxn << endl;
				for(auto [x,y] : dist[a]) {
					if(vis2[x][y]) continue;
					vis2[x][y] = true;
					for(int b = 0;b < 4;++b) {
						int w = to[x][y][b].first;
						int z = to[x][y][b].second;
						// if(i == 1 && j == 1 && w == 2 && z == 1) cout << i << " " << j << " " << b << " " << x << " " << y << " " << w << " " << z << endl;
						// cout << x << " " << y << endl;
						// cout << b << endl;
						if(dp[i][j][x][y] + 1 < dp[i][j][w][z]) {
							dp[i][j][w][z] = dp[i][j][x][y] + 1;
							vis[w][z] = true;
							dist[dp[i][j][w][z]].push_back({w,z});
							mxn = max(mxn,dp[i][j][w][z]);
						}
					}
				}
				dist[a].clear();
			}
		}
	}
	int ans = INF;
	for(int i = 1;i <= N;++i) {
		for(int j = 1;j <= M;++j) {
			ans = min(ans,dp[0][K - 1][i][j]);
		}
	}
	// cout << to[4][1][3].first << " " << to[4][1][3].second << endl;
	// cout << dp[1][1][1][1] << endl;
	cout << (ans >= INF ? -1 : ans) << endl;
	return 0;
}

Compilation message

robots.cpp: In function 'int main()':
robots.cpp:89:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   89 |     for(auto [x,y] : dist[a]) {
      |              ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 87328 KB Output is correct
2 Correct 31 ms 87372 KB Output is correct
3 Correct 31 ms 87340 KB Output is correct
4 Correct 32 ms 87444 KB Output is correct
5 Correct 40 ms 87464 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 87328 KB Output is correct
2 Correct 31 ms 87372 KB Output is correct
3 Correct 31 ms 87340 KB Output is correct
4 Correct 32 ms 87444 KB Output is correct
5 Correct 40 ms 87464 KB Output is correct
6 Correct 31 ms 87372 KB Output is correct
7 Correct 32 ms 87404 KB Output is correct
8 Correct 31 ms 87408 KB Output is correct
9 Correct 33 ms 87340 KB Output is correct
10 Correct 32 ms 87388 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 87328 KB Output is correct
2 Correct 31 ms 87372 KB Output is correct
3 Correct 31 ms 87340 KB Output is correct
4 Correct 32 ms 87444 KB Output is correct
5 Correct 40 ms 87464 KB Output is correct
6 Correct 31 ms 87372 KB Output is correct
7 Correct 32 ms 87404 KB Output is correct
8 Correct 31 ms 87408 KB Output is correct
9 Correct 33 ms 87340 KB Output is correct
10 Correct 32 ms 87388 KB Output is correct
11 Correct 89 ms 97640 KB Output is correct
12 Correct 51 ms 94364 KB Output is correct
13 Correct 47 ms 94592 KB Output is correct
14 Correct 163 ms 102892 KB Output is correct
15 Correct 77 ms 94976 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 87328 KB Output is correct
2 Correct 31 ms 87372 KB Output is correct
3 Correct 31 ms 87340 KB Output is correct
4 Correct 32 ms 87444 KB Output is correct
5 Correct 40 ms 87464 KB Output is correct
6 Correct 31 ms 87372 KB Output is correct
7 Correct 32 ms 87404 KB Output is correct
8 Correct 31 ms 87408 KB Output is correct
9 Correct 33 ms 87340 KB Output is correct
10 Correct 32 ms 87388 KB Output is correct
11 Correct 89 ms 97640 KB Output is correct
12 Correct 51 ms 94364 KB Output is correct
13 Correct 47 ms 94592 KB Output is correct
14 Correct 163 ms 102892 KB Output is correct
15 Correct 77 ms 94976 KB Output is correct
16 Correct 80 ms 108004 KB Output is correct
17 Correct 434 ms 134180 KB Output is correct
18 Correct 117 ms 105968 KB Output is correct
19 Correct 71 ms 101916 KB Output is correct
20 Correct 207 ms 116784 KB Output is correct