oj.uz

Submission #422082

# Submission time Handle Problem Language Result Execution time Memory
422082 2021-06-09T17:15:47 Z rqi Robots (APIO13_robots) C++14
60 / 100
 1500 ms 95384 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.tie(0)->sync_with_stdio(0);
	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 1 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 1 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 1 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 1 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 1 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 435 ms 53876 KB Output is correct
12 Correct 18 ms 5960 KB Output is correct
13 Correct 227 ms 35132 KB Output is correct
14 Correct 708 ms 54476 KB Output is correct
15 Correct 396 ms 53796 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 1 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 1 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 435 ms 53876 KB Output is correct
12 Correct 18 ms 5960 KB Output is correct
13 Correct 227 ms 35132 KB Output is correct
14 Correct 708 ms 54476 KB Output is correct
15 Correct 396 ms 53796 KB Output is correct
16 Execution timed out 1582 ms 95384 KB Time limit exceeded
17 Halted 0 ms 0 KB -