oj.uz

Submission #73667

# Submission time Handle Problem Language Result Execution time Memory
73667 2018-08-28T17:00:51 Z georgerapeanu Robots (APIO13_robots) C++11
30 / 100
 1500 ms 37888 KB 
#define JUDGE 1
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <queue>
#include <algorithm>

using namespace std;

#if JUDGE
FILE *f = stdin;
FILE *g = stdout;
#else
FILE *f = fopen("robots.in","r");
FILE *g = fopen("robots.out","w");
#endif
int n,w,h;
int dp[505][505][9][9];
pair<int,int> where_do_i_end[505][505][4];
char C[505][505];

const int dx[] = {-1,0,1,0};
const int dy[] = {0,1,0,-1};
const int inf = 1 << 28;

priority_queue< pair<int, pair<int,int> >, vector< pair<int, pair<int,int> > >,greater < pair<int, pair<int,int> > > > Q;

void push(int x,int y,int cost){
	Q.push(make_pair(cost,make_pair(x,y)));
}

void solve(int st,int dr){
	while(!Q.empty()){
		pair<int,int> pos = Q.top().second;
		int cost = Q.top().first;
		Q.pop();
		
		if(cost != dp[pos.first][pos.second][st][dr]){
			continue;
		}
		
		for(int k = 0;k < 4;k++){
			pair<int,int> npos = where_do_i_end[pos.first][pos.second][k];
			if(npos.first == -1 && npos.second == -1){
				continue;
			}
			
			if(dp[npos.first][npos.second][st][dr] > dp[pos.first][pos.second][st][dr] + 1){
				dp[npos.first][npos.second][st][dr] = dp[pos.first][pos.second][st][dr] + 1;
				Q.push({dp[npos.first][npos.second][st][dr],npos});
			}
		}
	}
}

int which_viz[505][505][4];
int last_viz;

pair<int,int> get_end(int i,int j,int k){
	if(where_do_i_end[i][j][k].first || where_do_i_end[i][j][k].second){
		return where_do_i_end[i][j][k];
	}
	
	if(C[i][j] == 'x'){
		where_do_i_end[i][j][k] = {-1,-1};
	}
	
	where_do_i_end[i][j][k] = {i,j};
	
	vector< pair<pair<int,int>,int> > V = {make_pair(make_pair(i,j),k)};
	which_viz[i][j][k] = ++last_viz;
	
	pair<int,int> ans = {-1,-1};
	
	
	for(int k = 0;k < (int)V.size();k++){
		int dir = (V[k].second + (C[V[k].first.first][V[k].first.second] == 'C') + (C[V[k].first.first][V[k].first.second] == 'A' ? 3:0)) & 3;
		int x = V[k].first.first + dx[dir];
		int y = V[k].first.second + dy[dir];
		
		if(!(x && y && x <= h && y <= w && C[x][y] != 'x')){
			ans = V[k].first;
			break;
		}
		
		else if(!which_viz[x][y][dir]){
			V.push_back({{x,y},dir});
			which_viz[x][y][dir] = last_viz;
		}
		
		else{
			if(which_viz[x][y][dir] != last_viz){
				ans = where_do_i_end[x][y][dir];
			}
			else{
				break;
			}
		}
	}
	
	for(auto it:V){
		where_do_i_end[it.first.first][it.first.second][it.second] = ans;
	}
	
	return where_do_i_end[i][j][k];
}

int main(){
	fscanf(f,"%d %d %d\n",&n,&w,&h);
	
	for(int i = 1;i <= h;i++){
		fgets(C[i] + 1,505,f);
	}
	
	
	for(int i = 1;i <= h;i++ ){
		for(int j = 1;j <= w;j++){
			for(int k = 0;k < 4;k++){
				where_do_i_end[i][j][k] = get_end(i,j,k);
			}
		}
	}
	
	for(int i = 1;i <= h;i++){
		for(int j = 1;j <= w;j++){
			for(int st = 0;st < n;st++){
				for(int dr = 0;dr < n;dr++){
					dp[i][j][st][dr] = inf;
				}
			}
		}
	}
	for(int i = 1;i <= h;i++){
		for(int j = 1;j <= w;j++){
			if('1' <= C[i][j] && C[i][j]  <= '9'){
				dp[i][j][C[i][j] - '1'][C[i][j] - '1'] = 0;
				push(i,j,0);
				solve(C[i][j] - '1',C[i][j] - '1');
			}
		}
	}
	for(int l = 1;l < 9;l++){
		for(int st = 0;st < n;st++){
			int dr = st + l;
			for(int i = 1;i <= h;i++){
				for(int j = 1;j <= w;j++){
						for(int k = st;k < dr;k++){
							dp[i][j][st][dr] = min(dp[i][j][st][k] + dp[i][j][k + 1][dr],dp[i][j][st][dr]);
						}
						push(i,j,dp[i][j][st][dr]);
				}
			}
			solve(st,dr);
		}
	}
	
	int ans = inf;
	
	for(int i = 1;i <= h;i++){
		for(int j = 1;j <= w;j++){
			if(ans > dp[i][j][0][n - 1]){
				ans = dp[i][j][0][n - 1];
			}
		}
	}

	fprintf(g,"%d\n",(ans == inf ? -1:ans));
	
	return 0;
}

Compilation message

robots.cpp: In function 'int main()':
robots.cpp:109:8: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  fscanf(f,"%d %d %d\n",&n,&w,&h);
  ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
robots.cpp:112:8: warning: ignoring return value of 'char* fgets(char*, int, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   fgets(C[i] + 1,505,f);
   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 484 KB Output is correct
3 Correct 3 ms 536 KB Output is correct
4 Correct 2 ms 612 KB Output is correct
5 Correct 3 ms 664 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 484 KB Output is correct
3 Correct 3 ms 536 KB Output is correct
4 Correct 2 ms 612 KB Output is correct
5 Correct 3 ms 664 KB Output is correct
6 Correct 2 ms 664 KB Output is correct
7 Correct 3 ms 664 KB Output is correct
8 Correct 2 ms 664 KB Output is correct
9 Correct 3 ms 664 KB Output is correct
10 Correct 2 ms 716 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 484 KB Output is correct
3 Correct 3 ms 536 KB Output is correct
4 Correct 2 ms 612 KB Output is correct
5 Correct 3 ms 664 KB Output is correct
6 Correct 2 ms 664 KB Output is correct
7 Correct 3 ms 664 KB Output is correct
8 Correct 2 ms 664 KB Output is correct
9 Correct 3 ms 664 KB Output is correct
10 Correct 2 ms 716 KB Output is correct
11 Execution timed out 1563 ms 37888 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 484 KB Output is correct
3 Correct 3 ms 536 KB Output is correct
4 Correct 2 ms 612 KB Output is correct
5 Correct 3 ms 664 KB Output is correct
6 Correct 2 ms 664 KB Output is correct
7 Correct 3 ms 664 KB Output is correct
8 Correct 2 ms 664 KB Output is correct
9 Correct 3 ms 664 KB Output is correct
10 Correct 2 ms 716 KB Output is correct
11 Execution timed out 1563 ms 37888 KB Time limit exceeded
12 Halted 0 ms 0 KB -