oj.uz

Submission #40405

# Submission time Handle Problem Language Result Execution time Memory
40405 2018-02-01T06:45:15 Z mohammad_kilani Robots (APIO13_robots) C++14
60 / 100
 1500 ms 63292 KB 
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define oo 1000000000
const double PI = acos(-1);
const int N = 501;
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< pair<int,pair<int,int> > > tmp;

deque < pair<int, pair<int,int> > > q;

inline void BFS(int low,int high){
	vi++;
	tmp.clear();
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			tmp.push_back(make_pair(best[idx[low][high]][i][j],make_pair(i,j)));
		}
	}
	sort(tmp.begin(),tmp.end());
	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)));
			}
		}
	}
}
 
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:25:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<tmp.size();i++){
               ^
robots.cpp:35: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:69: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:78: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 2 ms 508 KB Output is correct
2 Correct 2 ms 608 KB Output is correct
3 Correct 2 ms 680 KB Output is correct
4 Correct 3 ms 1612 KB Output is correct
5 Correct 2 ms 1764 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 508 KB Output is correct
2 Correct 2 ms 608 KB Output is correct
3 Correct 2 ms 680 KB Output is correct
4 Correct 3 ms 1612 KB Output is correct
5 Correct 2 ms 1764 KB Output is correct
6 Correct 2 ms 1764 KB Output is correct
7 Correct 2 ms 1764 KB Output is correct
8 Correct 2 ms 1764 KB Output is correct
9 Correct 2 ms 1764 KB Output is correct
10 Correct 3 ms 1764 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 508 KB Output is correct
2 Correct 2 ms 608 KB Output is correct
3 Correct 2 ms 680 KB Output is correct
4 Correct 3 ms 1612 KB Output is correct
5 Correct 2 ms 1764 KB Output is correct
6 Correct 2 ms 1764 KB Output is correct
7 Correct 2 ms 1764 KB Output is correct
8 Correct 2 ms 1764 KB Output is correct
9 Correct 2 ms 1764 KB Output is correct
10 Correct 3 ms 1764 KB Output is correct
11 Correct 527 ms 33728 KB Output is correct
12 Correct 36 ms 33728 KB Output is correct
13 Correct 314 ms 34252 KB Output is correct
14 Correct 538 ms 34252 KB Output is correct
15 Correct 422 ms 34252 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 508 KB Output is correct
2 Correct 2 ms 608 KB Output is correct
3 Correct 2 ms 680 KB Output is correct
4 Correct 3 ms 1612 KB Output is correct
5 Correct 2 ms 1764 KB Output is correct
6 Correct 2 ms 1764 KB Output is correct
7 Correct 2 ms 1764 KB Output is correct
8 Correct 2 ms 1764 KB Output is correct
9 Correct 2 ms 1764 KB Output is correct
10 Correct 3 ms 1764 KB Output is correct
11 Correct 527 ms 33728 KB Output is correct
12 Correct 36 ms 33728 KB Output is correct
13 Correct 314 ms 34252 KB Output is correct
14 Correct 538 ms 34252 KB Output is correct
15 Correct 422 ms 34252 KB Output is correct
16 Correct 1425 ms 63292 KB Output is correct
17 Execution timed out 1557 ms 63292 KB Time limit exceeded
18 Halted 0 ms 0 KB -