oj.uz

Submission #234001

# Submission time Handle Problem Language Result Execution time Memory
234001 2020-05-22T17:14:10 Z AQT Robots (APIO13_robots) C++14
60 / 100
 555 ms 163844 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 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: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 47 ms 66304 KB Output is correct
2 Correct 47 ms 66296 KB Output is correct
3 Correct 49 ms 66424 KB Output is correct
4 Correct 47 ms 66424 KB Output is correct
5 Correct 47 ms 66552 KB Output is correct

Subtask #2
20.0 / 20.0

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

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 66304 KB Output is correct
2 Correct 47 ms 66296 KB Output is correct
3 Correct 49 ms 66424 KB Output is correct
4 Correct 47 ms 66424 KB Output is correct
5 Correct 47 ms 66552 KB Output is correct
6 Correct 45 ms 66304 KB Output is correct
7 Correct 46 ms 66296 KB Output is correct
8 Correct 46 ms 66296 KB Output is correct
9 Correct 48 ms 66296 KB Output is correct
10 Correct 45 ms 66424 KB Output is correct
11 Correct 273 ms 111608 KB Output is correct
12 Correct 69 ms 76408 KB Output is correct
13 Correct 132 ms 92280 KB Output is correct
14 Correct 555 ms 140588 KB Output is correct
15 Correct 225 ms 106392 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 66304 KB Output is correct
2 Correct 47 ms 66296 KB Output is correct
3 Correct 49 ms 66424 KB Output is correct
4 Correct 47 ms 66424 KB Output is correct
5 Correct 47 ms 66552 KB Output is correct
6 Correct 45 ms 66304 KB Output is correct
7 Correct 46 ms 66296 KB Output is correct
8 Correct 46 ms 66296 KB Output is correct
9 Correct 48 ms 66296 KB Output is correct
10 Correct 45 ms 66424 KB Output is correct
11 Correct 273 ms 111608 KB Output is correct
12 Correct 69 ms 76408 KB Output is correct
13 Correct 132 ms 92280 KB Output is correct
14 Correct 555 ms 140588 KB Output is correct
15 Correct 225 ms 106392 KB Output is correct
16 Correct 435 ms 130936 KB Output is correct
17 Runtime error 416 ms 163844 KB Execution killed with signal 9 (could be triggered by violating memory limits)
18 Halted 0 ms 0 KB -