oj.uz

Submission #234002

# Submission time Handle Problem Language Result Execution time Memory
234002 2020-05-22T17:14:53 Z AQT Robots (APIO13_robots) C++14
100 / 100
 1025 ms 163272 KB 
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
// Problem : APIO '13 P1 - Robots
// Contest : DMOJ
// URL : https://dmoj.ca/problem/apio13p1
// Memory Limit : 128 MB
// Time Limit : 750 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)
 
#include <bits/stdc++.h>
 
using namespace std;
 
int K, N, M;
int dist[10][10][505][505];
vector<pair<int, int>> graph[505][505];
char mp[505][505];
pair<int, int> moves[4] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
pair<int, int> endpos[4][505][505];
vector<pair<int, int>> vec[505*505*10];
int oo = INT_MAX>>2;
 
pair<int, int> fnd(int d, int x, int y){
	if(endpos[d][x][y].first){
		return endpos[d][x][y];
	}
	int r = 0;
	if(mp[x][y] == 'A'){
		r = 3;
	}
	if(mp[x][y] == 'C'){
		r = 1;
	}
	if(mp[x+moves[(d+r)%4].first][y+moves[(d+r)%4].second] == 'x'){
		return endpos[d][x][y] = {x, y};
	}
	return endpos[d][x][y] = fnd((d+r)%4, x+moves[(d+r)%4].first, y+moves[(d+r)%4].second);
}
 
int main(){
	cin.sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> K >> M >> N;
	oo = K*M*N;
	for(int l = 1; l<=K; l++){
		for(int r = l; r<=K; r++){
			for(int i = 1; i<=N; i++){
				for(int j = 1; j<=M; j++){
					dist[l][r][i][j] = oo;
				}
			}		
		}
	}
	for(int i = 1; i<=N; i++){
		for(int j = 1; j<=M; j++){
			cin >> mp[i][j];
			if(mp[i][j] > '0' && mp[i][j] <= '9'){
				dist[mp[i][j]-'0'][mp[i][j]-'0'][i][j] = 0;
			}
		}
	}
	for(int i = 0; i<=N+1; i++){
		mp[i][0] = mp[i][M+1] = 'x';
	}
	for(int j = 0; j<=M+1; j++){
		mp[0][j] = mp[N+1][j] = 'x';
	}
	for(int i = 1; i<=N; i++){
		for(int j = 1; j<=M; j++){
			for(int k = 0; k<4; k++){
				graph[i][j].push_back(fnd(k, i, j));
			}
		}
	}
	for(int len = 1; len<=K; len++){
		for(int l = 1; l+len-1<=K; l++){
			int r = l+len-1;
			for(int d = 0; d<=oo; d++){
				vec[d].clear();
			}
			for(int i = 1; i<=N; i++){
				for(int j = 1; j<=M; j++){
					for(int k = l; k<r; k++){
						dist[l][r][i][j] = min(dist[l][k][i][j] + dist[k+1][r][i][j], dist[l][r][i][j]);
					}
					if(dist[l][r][i][j] != oo){
						//pq.push({dist[l][r][i][j], {i, j}});
						vec[dist[l][r][i][j]].emplace_back(i, j);
					}
				}
			}
			/*
			while(pq.size()){
				auto p = pq.top();
				pq.pop();
				if(dist[l][r][p.second.first][p.second.second] != p.first){
					continue;
				}
				for(auto e : graph[p.second.first][p.second.second]){
					if(dist[l][r][e.first][e.second] > dist[l][r][p.second.first][p.second.second] + 1){
						dist[l][r][e.first][e.second] = dist[l][r][p.second.first][p.second.second] + 1;
						pq.push({dist[l][r][e.first][e.second], {e.first, e.second}});
					}
				}
			}
			*/
			for(int d = 0; d<=oo; d++){
				for(auto p : vec[d]){
					if(dist[l][r][p.first][p.second] != d){
						continue;
					}
					for(auto e : graph[p.first][p.second]){
						if(dist[l][r][e.first][e.second] > d+1){
							dist[l][r][e.first][e.second] = d+1;
							vec[d+1].emplace_back(e.first, e.second);
						}
					}
				}
			}
		}
	}
	int ans = oo;
	for(int i = 1; i<=N; i++){
		for(int j = 1; j<=M; j++){
			ans = min(dist[1][K][i][j], ans);
		}
	}
	/*
	for(int l = 1; l<=K; l++){
		for(int r = l; r<=K; r++){
			cout << l << " " << r << "\n";
			for(int i = 1; i<=N; i++){
				for(int j = 1; j<=M; j++){
					if(dist[l][r][i][j] == INT_MAX>>2){
						cout << 'X';
					}
					else{
						cout << dist[l][r][i][j];
					}
				}
				cout << "\n";
			}
			cout << "\n";
		}
	}
	*/
	cout << (ans == oo ? -1 : ans);
}

Compilation message

robots.cpp: In function 'int main()':
robots.cpp:85:60: warning: array subscript is above array bounds [-Warray-bounds]
       dist[l][r][i][j] = min(dist[l][k][i][j] + dist[k+1][r][i][j], dist[l][r][i][j]);
                                                 ~~~~~~~~~~~^
robots.cpp:85:57: warning: array subscript is above array bounds [-Warray-bounds]
       dist[l][r][i][j] = min(dist[l][k][i][j] + dist[k+1][r][i][j], dist[l][r][i][j]);
                                                 ~~~~~~~~^
robots.cpp:85:16: warning: array subscript is above array bounds [-Warray-bounds]
       dist[l][r][i][j] = min(dist[l][k][i][j] + dist[k+1][r][i][j], dist[l][r][i][j]);
       ~~~~~~~~~^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 66296 KB Output is correct
2 Correct 45 ms 66304 KB Output is correct
3 Correct 46 ms 66304 KB Output is correct
4 Correct 46 ms 66432 KB Output is correct
5 Correct 46 ms 66556 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 66296 KB Output is correct
2 Correct 45 ms 66304 KB Output is correct
3 Correct 46 ms 66304 KB Output is correct
4 Correct 46 ms 66432 KB Output is correct
5 Correct 46 ms 66556 KB Output is correct
6 Correct 47 ms 66296 KB Output is correct
7 Correct 49 ms 66296 KB Output is correct
8 Correct 47 ms 66296 KB Output is correct
9 Correct 46 ms 66296 KB Output is correct
10 Correct 45 ms 66560 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 66296 KB Output is correct
2 Correct 45 ms 66304 KB Output is correct
3 Correct 46 ms 66304 KB Output is correct
4 Correct 46 ms 66432 KB Output is correct
5 Correct 46 ms 66556 KB Output is correct
6 Correct 47 ms 66296 KB Output is correct
7 Correct 49 ms 66296 KB Output is correct
8 Correct 47 ms 66296 KB Output is correct
9 Correct 46 ms 66296 KB Output is correct
10 Correct 45 ms 66560 KB Output is correct
11 Correct 304 ms 105932 KB Output is correct
12 Correct 71 ms 76408 KB Output is correct
13 Correct 168 ms 92152 KB Output is correct
14 Correct 384 ms 111096 KB Output is correct
15 Correct 283 ms 103200 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 66296 KB Output is correct
2 Correct 45 ms 66304 KB Output is correct
3 Correct 46 ms 66304 KB Output is correct
4 Correct 46 ms 66432 KB Output is correct
5 Correct 46 ms 66556 KB Output is correct
6 Correct 47 ms 66296 KB Output is correct
7 Correct 49 ms 66296 KB Output is correct
8 Correct 47 ms 66296 KB Output is correct
9 Correct 46 ms 66296 KB Output is correct
10 Correct 45 ms 66560 KB Output is correct
11 Correct 304 ms 105932 KB Output is correct
12 Correct 71 ms 76408 KB Output is correct
13 Correct 168 ms 92152 KB Output is correct
14 Correct 384 ms 111096 KB Output is correct
15 Correct 283 ms 103200 KB Output is correct
16 Correct 653 ms 130808 KB Output is correct
17 Correct 1025 ms 163272 KB Output is correct
18 Correct 676 ms 135152 KB Output is correct
19 Correct 653 ms 131372 KB Output is correct
20 Correct 795 ms 146028 KB Output is correct