oj.uz

Submission #233998

# Submission time Handle Problem Language Result Execution time Memory
233998 2020-05-22T17:03:16 Z AQT Robots (APIO13_robots) C++14
60 / 100
 1500 ms 72484 KB 
// 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);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 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 8 ms 6656 KB Output is correct
5 Correct 8 ms 6528 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 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 8 ms 6656 KB Output is correct
5 Correct 8 ms 6528 KB Output is correct
6 Correct 9 ms 6400 KB Output is correct
7 Correct 8 ms 6400 KB Output is correct
8 Correct 8 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 8 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 8 ms 6656 KB Output is correct
5 Correct 8 ms 6528 KB Output is correct
6 Correct 9 ms 6400 KB Output is correct
7 Correct 8 ms 6400 KB Output is correct
8 Correct 8 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 168 ms 42612 KB Output is correct
12 Correct 34 ms 15996 KB Output is correct
13 Correct 57 ms 32248 KB Output is correct
14 Correct 673 ms 42996 KB Output is correct
15 Correct 110 ms 42424 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 8 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 8 ms 6656 KB Output is correct
5 Correct 8 ms 6528 KB Output is correct
6 Correct 9 ms 6400 KB Output is correct
7 Correct 8 ms 6400 KB Output is correct
8 Correct 8 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 168 ms 42612 KB Output is correct
12 Correct 34 ms 15996 KB Output is correct
13 Correct 57 ms 32248 KB Output is correct
14 Correct 673 ms 42996 KB Output is correct
15 Correct 110 ms 42424 KB Output is correct
16 Correct 156 ms 70904 KB Output is correct
17 Execution timed out 1595 ms 72484 KB Time limit exceeded
18 Halted 0 ms 0 KB -