oj.uz

Submission #422084

# Submission time Handle Problem Language Result Execution time Memory
422084 2021-06-09T17:19:34 Z rqi Robots (APIO13_robots) C++14
60 / 100
 1500 ms 93324 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];
//vi dist_poses[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;
					if(dist[L][R][i][j] != MOD){
						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 1 ms 332 KB Output is correct
8 Correct 1 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 1 ms 332 KB Output is correct
8 Correct 1 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 149 ms 53096 KB Output is correct
12 Correct 7 ms 4940 KB Output is correct
13 Correct 34 ms 33732 KB Output is correct
14 Correct 618 ms 54352 KB Output is correct
15 Correct 112 ms 52828 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 1 ms 332 KB Output is correct
8 Correct 1 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 149 ms 53096 KB Output is correct
12 Correct 7 ms 4940 KB Output is correct
13 Correct 34 ms 33732 KB Output is correct
14 Correct 618 ms 54352 KB Output is correct
15 Correct 112 ms 52828 KB Output is correct
16 Correct 143 ms 89268 KB Output is correct
17 Execution timed out 1598 ms 93324 KB Time limit exceeded
18 Halted 0 ms 0 KB -