oj.uz

Submission #233999

# Submission time Handle Problem Language Result Execution time Memory
233999 2020-05-22T17:08:03 Z AQT Robots (APIO13_robots) C++14
60 / 100
 1500 ms 72560 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];
priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> pq;
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 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}});
					}
				}
			}
			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}});
					}
				}
			}
		}
	}
	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:82: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:82: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:82: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 9 ms 6400 KB Output is correct
2 Correct 8 ms 6400 KB Output is correct
3 Correct 8 ms 6400 KB Output is correct
4 Correct 9 ms 6656 KB Output is correct
5 Correct 9 ms 6528 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 6400 KB Output is correct
2 Correct 8 ms 6400 KB Output is correct
3 Correct 8 ms 6400 KB Output is correct
4 Correct 9 ms 6656 KB Output is correct
5 Correct 9 ms 6528 KB Output is correct
6 Correct 11 ms 6400 KB Output is correct
7 Correct 9 ms 6400 KB Output is correct
8 Correct 10 ms 6400 KB Output is correct
9 Correct 8 ms 6400 KB Output is correct
10 Correct 8 ms 6528 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 6400 KB Output is correct
2 Correct 8 ms 6400 KB Output is correct
3 Correct 8 ms 6400 KB Output is correct
4 Correct 9 ms 6656 KB Output is correct
5 Correct 9 ms 6528 KB Output is correct
6 Correct 11 ms 6400 KB Output is correct
7 Correct 9 ms 6400 KB Output is correct
8 Correct 10 ms 6400 KB Output is correct
9 Correct 8 ms 6400 KB Output is correct
10 Correct 8 ms 6528 KB Output is correct
11 Correct 162 ms 42552 KB Output is correct
12 Correct 31 ms 16000 KB Output is correct
13 Correct 51 ms 32248 KB Output is correct
14 Correct 631 ms 42996 KB Output is correct
15 Correct 101 ms 42424 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 6400 KB Output is correct
2 Correct 8 ms 6400 KB Output is correct
3 Correct 8 ms 6400 KB Output is correct
4 Correct 9 ms 6656 KB Output is correct
5 Correct 9 ms 6528 KB Output is correct
6 Correct 11 ms 6400 KB Output is correct
7 Correct 9 ms 6400 KB Output is correct
8 Correct 10 ms 6400 KB Output is correct
9 Correct 8 ms 6400 KB Output is correct
10 Correct 8 ms 6528 KB Output is correct
11 Correct 162 ms 42552 KB Output is correct
12 Correct 31 ms 16000 KB Output is correct
13 Correct 51 ms 32248 KB Output is correct
14 Correct 631 ms 42996 KB Output is correct
15 Correct 101 ms 42424 KB Output is correct
16 Correct 135 ms 70904 KB Output is correct
17 Execution timed out 1591 ms 72560 KB Time limit exceeded
18 Halted 0 ms 0 KB -