oj.uz

Submission #422081

# Submission time Handle Problem Language Result Execution time Memory
422081 2021-06-09T17:14:42 Z rqi Robots (APIO13_robots) C++14
60 / 100
 1500 ms 95588 KB 
#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vi;
typedef pair<int, int> pi;
typedef long long ll;
typedef vector<ll> vl;

#define pb push_back
#define bk back()
#define sz(x) (int)(x).size()
#define f first
#define s second
#define mp make_pair

void ckmin(int& a, int b){
	a = min(a, b);
}

const int MOD = 1e9+7;

vi dx = vi{1, 0, -1, 0};
vi dy = vi{0, 1, 0, -1};

const int mx = 505;
int n, w, h;
bool wall[mx][mx];
pi adj[mx][mx][4]; //-3 is unknown, -2 is in progress, -1 is bad
pi initial_pos[10];
int dir[mx][mx];

void genTrans(int X, int Y, int d){
	if(adj[X][Y][d] != mp(-3, -3)) return;
	if(wall[X+dx[d]][Y+dy[d]]){
		adj[X][Y][d] = mp(X, Y);
		return;
	}
	adj[X][Y][d] = mp(-2, -2);
	int new_X = X+dx[d];
	int new_Y = Y+dy[d];
	int new_d = (d+dir[new_X][new_Y]+4) % 4;
	if(adj[new_X][new_Y][new_d] == mp(-2, -2)){
		adj[X][Y][d] = mp(-1, -1);
		return;
	}
	genTrans(new_X, new_Y, new_d);
	adj[X][Y][d] = adj[new_X][new_Y][new_d];
}

int dist[10][10][mx][mx];

void PRINT(pi& a){
	cout << "(" << a.f << ", " << a.s << ")" << "\n";
}

int main(){
	cin >> n >> w >> h;

	for(int i = 1; i <= h; i++){
		string s;
		cin >> s;
		for(int j = 1; j <= w; j++){
			if(s[j-1] == 'x'){
				wall[i][j] = 1;
			}
			else if('1' <= s[j-1] && s[j-1] <= '9'){
				initial_pos[s[j-1]-'0'] = mp(i, j);
			}
			else if(s[j-1] == 'A'){
				dir[i][j] = 1;
			}
			else if(s[j-1] == 'C'){
				dir[i][j] = -1;
			}
		}
	}

	for(int i = 1; i <= h; i++){
		for(int j = 1; j <= w; j++){
			for(int d = 0; d < 4; d++){
				adj[i][j][d] = mp(-3, -3);
			}
		}
	}

	for(int i = 0; i <= h+1; i++){
		wall[i][0] = wall[i][w+1] = 1;
	}

	for(int i = 0; i <= w+1; i++){
		wall[0][i] = wall[h+1][i] = 1;
	}

	for(int i = 1; i <= h; i++){
		for(int j = 1; j <= w; j++){
			if(wall[i][j]) continue;
			for(int d = 0; d < 4; d++){
				genTrans(i, j, d);
			}
		}
	}




	for(int L = 1; L <= n; L++){
		for(int R = 1; R <= n; R++){
			for(int i = 1; i <= h; i++){
				for(int j = 1; j <= w; j++){
					if(wall[i][j]) continue;
					dist[L][R][i][j] = MOD;
				}
			}
		}
	}

	for(int L = 1; L <= n; L++){
		dist[L][L][initial_pos[L].f][initial_pos[L].s] = 0;
	}

	// for(int i = 1; i <= h; i++){
	// 	for(int j = 1; j <= w; j++){
	// 		for(int d = 0; d < 4; d++){
	// 			if(adj[i][j][d] != mp(-1, -1)){
	// 				cout << i << " " << j << " " << d << " " << adj[i][j][d].f << " " << adj[i][j][d].s << "\n";
	// 			}
	// 		}
	// 	}
	// }


	for(int SZ = 0; SZ <= n-1; SZ++){
		for(int L = 1; L+SZ <= n; L++){
			int R = L+SZ;

			
			for(int MID = L; MID+1 <= R; MID++){
				for(int i = 1; i <= h; i++){
					for(int j = 1; j <= w; j++){
						if(wall[i][j]) continue;
						ckmin(dist[L][R][i][j], dist[L][MID][i][j]+dist[MID+1][R][i][j]);
					}
				}
			}
			
			priority_queue<pair<int, pi>, vector<pair<int, pi>>, greater<pair<int, pi>>> pq; //distance, position
			for(int i = 1; i <= h; i++){
				for(int j = 1; j <= w; j++){
					if(wall[i][j]) continue;
					pq.push(mp(dist[L][R][i][j], mp(i, j)));
				}
			}
			while(sz(pq)){
				int DIST = pq.top().f;
				pi pos = pq.top().s;
				pq.pop();
				if(dist[L][R][pos.f][pos.s] < DIST) continue;


				assert(dist[L][R][pos.f][pos.s] == DIST);

				for(int d = 0; d < 4; d++){
					if(adj[pos.f][pos.s][d] == mp(-1, -1)) continue;
					pi new_pos = adj[pos.f][pos.s][d];

					if(dist[L][R][new_pos.f][new_pos.s] <= DIST+1) continue;
					dist[L][R][new_pos.f][new_pos.s] = DIST+1;
					pq.push(mp(DIST+1, new_pos));
				}
			}
			
		}
	}
	
	// cout << dist[3][3][1][7] << "\n";
	// cout << dist[4][4][1][7] << "\n";
	// cout << dist[3][4][1][7] << "\n";

	int ans = MOD;
	for(int i = 1; i <= h; i++){
		for(int j = 1; j <= w; j++){
			if(wall[i][j]) continue;
			ckmin(ans, dist[1][n][i][j]);
		}
	}

	if(ans == MOD){
		cout << -1 << "\n";
	}
	else{
		cout << ans << "\n";
	}

	

}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 0 ms 332 KB Output is correct
8 Correct 0 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 460 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 0 ms 332 KB Output is correct
8 Correct 0 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 466 ms 53676 KB Output is correct
12 Correct 18 ms 5964 KB Output is correct
13 Correct 237 ms 35180 KB Output is correct
14 Correct 704 ms 54344 KB Output is correct
15 Correct 396 ms 53916 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 0 ms 332 KB Output is correct
8 Correct 0 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 466 ms 53676 KB Output is correct
12 Correct 18 ms 5964 KB Output is correct
13 Correct 237 ms 35180 KB Output is correct
14 Correct 704 ms 54344 KB Output is correct
15 Correct 396 ms 53916 KB Output is correct
16 Execution timed out 1586 ms 95588 KB Time limit exceeded
17 Halted 0 ms 0 KB -