oj.uz

Submission #40406

# Submission time Handle Problem Language Result Execution time Memory
40406 2018-02-01T06:54:37 Z mohammad_kilani Robots (APIO13_robots) C++14
100 / 100
 1282 ms 85344 KB 
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define oo 1000000000
const double PI = acos(-1);
const int N = 501 , MAX_COST = 500 * 260 * 9 + 1;
char grid[N][N];
int n , m , sr , sc, cnt = 0 , idx[10][10] , num , vis[N][N] , vi = 1 , row , col , nr ,nc , cost , best[50][N][N];
int dr[4] = {1,0,-1,0};
int dc[4] = {0,1,0,-1};
pair<int,int> nxt[N][N][4]; 
vector< vector< pair<int,int> > > tmp2;
vector< pair<int,pair<int,int> > > tmp;
deque < pair<int, pair<int,int> > > q;

inline void BFS(int low,int high){
	vi++;
	tmp.clear();
	tmp2.clear();
	tmp2.resize(MAX_COST);
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if(best[idx[low][high]][i][j] == oo) continue;
			tmp2[best[idx[low][high]][i][j]].push_back(make_pair(i,j));
		}
	}
	for(int i=0;i<MAX_COST;i++)
		for(int j=0;j<tmp2[i].size();j++){
			tmp.push_back(make_pair(i,tmp2[i][j]));
		}
	for(int i=0;i<tmp.size();i++){
		q.push_back(tmp[i]);
		while(!q.empty()){
			cost = q.back().first;
			row = q.back().second.first;
			col = q.back().second.second;
			q.pop_back();
			if(vis[row][col] == vi) continue;
			vis[row][col] = vi;
			best[idx[low][high]][row][col] = cost;
			while(i + 1 < tmp.size() && tmp[i + 1].first == cost){
				i++;
				if(vis[tmp[i].second.first][tmp[i].second.second] == vi) continue;
				q.push_back(tmp[i]);
			}
			for(int i=0;i<4;i++){
				nr = nxt[row][col][i].first;
				nc = nxt[row][col][i].second;
				if(nr == -1 || vis[nr][nc] == vi) continue;
				q.push_front(make_pair(cost + 1 , make_pair(nr,nc)));
			}
		}
	}
}
 
inline void make(int r,int c,int k){
	sr = r;
	sc = c;
	while(r >= 0 && r < n && c >= 0 && c < m && grid[r][c] != 'x'){
		if(grid[r][c] == 'A') k--; else if(grid[r][c] == 'C') k++;
		if(k == -1) k = 3;
		if(k == 4) k = 0;
		nxt[r][c][k] = make_pair(sr,sc);
		r = r + dr[k];
		c = c + dc[k];
	}
}
 
int main(){
	for(int i=1;i<10;i++){
		for(int j=i;j<10;j++){
			idx[i][j] = cnt++;
		}
	}
	scanf("%d%d%d",&num,&m,&n);
	for(int i=0;i<cnt;i++){
		for(int j=0;j<n;j++){
			for(int k=0;k<m;k++){
				best[i][j][k] = oo;
			}
		}
	}
	for(int i=0;i<n;i++)
		scanf("%s",grid[i]);
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if(grid[i][j] >= '1' && grid[i][j] <= '9'){
				best[idx[grid[i][j]-'0'][grid[i][j]-'0']][i][j] = 0;
			}
			for(int k=0;k<4;k++)
				nxt[i][j][k] = make_pair(-1,-1);
		}
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if(grid[i][j] == 'x') continue;
			sr = i;
			sc = j;
			for(int k=0;k<4;k++){
				int nr = i + dr[k];
				int nc = j + dc[k];
				if(nr == -1 || nr == n || nc == -1 || nc == m || grid[nr][nc] == 'x'){
					make(i,j,(k + 2) % 4);
				}
			}
		}
	}
	for(int i=0;i<num;i++){
		for(int j=1;j+i<=num;j++){
			for(int row=0;row<n;row++){
				for(int col=0;col<m;col++){
					for(int k=j;k<j+i;k++){
						best[idx[j][i+j]][row][col] = min(best[idx[j][i+j]][row][col],best[idx[j][k]][row][col] + best[idx[k+1][i+j]][row][col]);
					}
				}
			}
			BFS(j,j+i);
		}
	}
	int ans = oo;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			ans = min(ans,best[idx[1][num]][i][j]);
		}
	}
	if(ans == oo) ans = -1;
	cout << ans << endl;
 	return 0;
}

Compilation message

robots.cpp: In function 'void BFS(int, int)':
robots.cpp:28:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<tmp2[i].size();j++){
                ^
robots.cpp:31:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<tmp.size();i++){
               ^
robots.cpp:41:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(i + 1 < tmp.size() && tmp[i + 1].first == cost){
                ^
robots.cpp: In function 'int main()':
robots.cpp:75:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d",&num,&m,&n);
                            ^
robots.cpp:84:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s",grid[i]);
                      ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 28024 KB Output is correct
2 Correct 51 ms 28176 KB Output is correct
3 Correct 50 ms 28176 KB Output is correct
4 Correct 43 ms 29040 KB Output is correct
5 Correct 44 ms 29076 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 28024 KB Output is correct
2 Correct 51 ms 28176 KB Output is correct
3 Correct 50 ms 28176 KB Output is correct
4 Correct 43 ms 29040 KB Output is correct
5 Correct 44 ms 29076 KB Output is correct
6 Correct 48 ms 29076 KB Output is correct
7 Correct 45 ms 29076 KB Output is correct
8 Correct 49 ms 29076 KB Output is correct
9 Correct 50 ms 29076 KB Output is correct
10 Correct 51 ms 29220 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 28024 KB Output is correct
2 Correct 51 ms 28176 KB Output is correct
3 Correct 50 ms 28176 KB Output is correct
4 Correct 43 ms 29040 KB Output is correct
5 Correct 44 ms 29076 KB Output is correct
6 Correct 48 ms 29076 KB Output is correct
7 Correct 45 ms 29076 KB Output is correct
8 Correct 49 ms 29076 KB Output is correct
9 Correct 50 ms 29076 KB Output is correct
10 Correct 51 ms 29220 KB Output is correct
11 Correct 686 ms 60348 KB Output is correct
12 Correct 54 ms 60348 KB Output is correct
13 Correct 389 ms 60348 KB Output is correct
14 Correct 759 ms 60716 KB Output is correct
15 Correct 603 ms 60716 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 28024 KB Output is correct
2 Correct 51 ms 28176 KB Output is correct
3 Correct 50 ms 28176 KB Output is correct
4 Correct 43 ms 29040 KB Output is correct
5 Correct 44 ms 29076 KB Output is correct
6 Correct 48 ms 29076 KB Output is correct
7 Correct 45 ms 29076 KB Output is correct
8 Correct 49 ms 29076 KB Output is correct
9 Correct 50 ms 29076 KB Output is correct
10 Correct 51 ms 29220 KB Output is correct
11 Correct 686 ms 60348 KB Output is correct
12 Correct 54 ms 60348 KB Output is correct
13 Correct 389 ms 60348 KB Output is correct
14 Correct 759 ms 60716 KB Output is correct
15 Correct 603 ms 60716 KB Output is correct
16 Correct 751 ms 81016 KB Output is correct
17 Correct 1282 ms 85344 KB Output is correct
18 Correct 765 ms 85344 KB Output is correct
19 Correct 727 ms 85344 KB Output is correct
20 Correct 1168 ms 85344 KB Output is correct