oj.uz

Submission #40407

# Submission time Handle Problem Language Result Execution time Memory
40407 2018-02-01T07:11:17 Z mohammad_kilani Robots (APIO13_robots) C++14
60 / 100
 474 ms 121032 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 * 30 * 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 5 ms 3704 KB Output is correct
2 Correct 5 ms 3808 KB Output is correct
3 Correct 5 ms 3880 KB Output is correct
4 Correct 5 ms 4672 KB Output is correct
5 Correct 6 ms 4836 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3704 KB Output is correct
2 Correct 5 ms 3808 KB Output is correct
3 Correct 5 ms 3880 KB Output is correct
4 Correct 5 ms 4672 KB Output is correct
5 Correct 6 ms 4836 KB Output is correct
6 Correct 5 ms 4836 KB Output is correct
7 Correct 5 ms 4836 KB Output is correct
8 Correct 6 ms 4836 KB Output is correct
9 Correct 5 ms 4836 KB Output is correct
10 Correct 6 ms 4836 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3704 KB Output is correct
2 Correct 5 ms 3808 KB Output is correct
3 Correct 5 ms 3880 KB Output is correct
4 Correct 5 ms 4672 KB Output is correct
5 Correct 6 ms 4836 KB Output is correct
6 Correct 5 ms 4836 KB Output is correct
7 Correct 5 ms 4836 KB Output is correct
8 Correct 6 ms 4836 KB Output is correct
9 Correct 5 ms 4836 KB Output is correct
10 Correct 6 ms 4836 KB Output is correct
11 Correct 156 ms 35812 KB Output is correct
12 Correct 30 ms 35812 KB Output is correct
13 Correct 77 ms 35812 KB Output is correct
14 Correct 263 ms 36428 KB Output is correct
15 Correct 118 ms 36428 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3704 KB Output is correct
2 Correct 5 ms 3808 KB Output is correct
3 Correct 5 ms 3880 KB Output is correct
4 Correct 5 ms 4672 KB Output is correct
5 Correct 6 ms 4836 KB Output is correct
6 Correct 5 ms 4836 KB Output is correct
7 Correct 5 ms 4836 KB Output is correct
8 Correct 6 ms 4836 KB Output is correct
9 Correct 5 ms 4836 KB Output is correct
10 Correct 6 ms 4836 KB Output is correct
11 Correct 156 ms 35812 KB Output is correct
12 Correct 30 ms 35812 KB Output is correct
13 Correct 77 ms 35812 KB Output is correct
14 Correct 263 ms 36428 KB Output is correct
15 Correct 118 ms 36428 KB Output is correct
16 Correct 214 ms 56652 KB Output is correct
17 Runtime error 474 ms 121032 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Halted 0 ms 0 KB -