oj.uz

Submission #234003

# Submission time Handle Problem Language Result Execution time Memory
234003 2020-05-22T18:01:50 Z AQT Robots (APIO13_robots) C++14
100 / 100
 576 ms 50420 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];
char mp[505][505];
pair<short, short> moves[4] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
pair<short, short> endpos[4][505][505];
queue<pair<short, short>> qu;
vector<pair<int, pair<short, short>>> vec;
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++){
				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;
			vec.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){
						vec.push_back({dist[l][r][i][j], make_pair(i, j)});
					}
				}
			}
			sort(vec.begin(), vec.end());
			if(vec.empty()){
				cout << -1 << "\n";
				return 0;
			}
			int idx = 0;
			while(qu.size() || idx < vec.size()){
				if(qu.empty()){
					qu.push(vec[idx++].second);
				}
				else{
					auto p = qu.front();
					qu.pop();
					while(idx < vec.size() && dist[l][r][p.first][p.second] == vec[idx].first){
						if(dist[l][r][vec[idx].second.first][vec[idx].second.second] == dist[l][r][p.first][p.second]){
							qu.push(vec[idx].second);
						}
						idx++;
					}
					for(int m = 0; m<4; m++){
						auto e = endpos[m][p.first][p.second];
						if(dist[l][r][e.first][e.second] > dist[l][r][p.first][p.second]+1){
							dist[l][r][e.first][e.second] = dist[l][r][p.first][p.second]+1;
							qu.push(e);
						}
					}					
				}
			}
		}
	}
	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);
		}
	}
	cout << (ans == oo ? -1 : ans);
}

Compilation message

robots.cpp: In function 'int main()':
robots.cpp:96:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(qu.size() || idx < vec.size()){
                       ~~~~^~~~~~~~~~~~
robots.cpp:103:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      while(idx < vec.size() && dist[l][r][p.first][p.second] == vec[idx].first){
            ~~~~^~~~~~~~~~~~
robots.cpp:83: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:83: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:83: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 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 512 KB Output is correct
5 Correct 5 ms 512 KB Output is correct

Subtask #2
20.0 / 20.0

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

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 512 KB Output is correct
5 Correct 5 ms 512 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 4 ms 512 KB Output is correct
11 Correct 88 ms 29952 KB Output is correct
12 Correct 10 ms 3456 KB Output is correct
13 Correct 28 ms 19584 KB Output is correct
14 Correct 210 ms 30208 KB Output is correct
15 Correct 27 ms 29824 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 512 KB Output is correct
5 Correct 5 ms 512 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 4 ms 512 KB Output is correct
11 Correct 88 ms 29952 KB Output is correct
12 Correct 10 ms 3456 KB Output is correct
13 Correct 28 ms 19584 KB Output is correct
14 Correct 210 ms 30208 KB Output is correct
15 Correct 27 ms 29824 KB Output is correct
16 Correct 88 ms 49272 KB Output is correct
17 Correct 576 ms 50420 KB Output is correct
18 Correct 56 ms 49912 KB Output is correct
19 Correct 86 ms 49280 KB Output is correct
20 Correct 345 ms 50420 KB Output is correct