oj.uz

Submission #154299

# Submission time Handle Problem Language Result Execution time Memory
154299 2019-09-20T11:29:53 Z two_sides Robots (APIO13_robots) C++17
100 / 100
 592 ms 101172 KB 
#include <bits/stdc++.h>
#define eb emplace_back
#define INF (0x3f3f3f3f)
using namespace std;
const int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
inline void fuk() { puts("-1"); exit(0); }
 
int D[9][9][505][505];
 
int PY[505][505][4], PX[505][505][4];
char A[505][505];
 
int N, H, W, Ans = INF;
 
vector<int> EV[505*505];
void spread(int D[][505]) {
	int mn = INF;
	for(int i = 1; i <= H; i++) for(int j = 1; j <= W; j++)
		if(D[i][j] < mn) mn = D[i][j];
	if(INF <= mn) fuk();
	for(int i = 1; i <= H; i++) for(int j = 1; j <= W; j++)
		if(D[i][j] <= mn + H*W)
			EV[D[i][j]-mn].eb(i<<10|j);
	for(int l = 0; l <= H*W; l++) {
		auto &V = EV[l];
		for(int key : V) {
			int i = key>>10, j = key&((1<<10)-1);
			for(int dr = 0, ni, nj; dr < 4; dr++) {
				ni = PY[i][j][dr]; nj = PX[i][j][dr];
				if(ni < 1 || nj < 1 || H < ni || W < nj) continue;
				if(D[ni][nj] <= mn+l+1) continue;
				D[ni][nj] = mn+l+1;
				EV[l+1].eb(ni<<10|nj);
			}
		}
		V.clear();
	}
}
 
void f(int y, int x, int dr) {
	int ndr = dr;
	if('A' == A[y][x]) ndr++;
	if('C' == A[y][x]) ndr--;
	if(ndr < 0) ndr = 3; if(3 < ndr) ndr = 0;
	PY[y][x][dr] = PX[y][x][dr] = -1;
	int ny = y+dy[ndr], nx = x+dx[ndr];
	if(!ny || !nx || H < ny || W < nx || 'x' == A[ny][nx]) {
		PY[y][x][dr] = y;
		PX[y][x][dr] = x;
		return;
	}
	if(!PY[ny][nx][ndr]) f(ny, nx, ndr);
	PY[y][x][dr] = PY[ny][nx][ndr];
	PX[y][x][dr] = PX[ny][nx][ndr];
}
 
int main() {
	scanf("%d%d%d", &N, &W, &H);
	for(int i = 1; i <= H; i++) scanf(" %s", A[i]+1);
	for(int i = 1; i <= H; i++) for(int j = 1; j <= W; j++) if('x' != A[i][j])
		for(int dr = 0; dr < 4; dr++) if(!PY[i][j][dr]) f(i, j, dr);
	fill(D[0][0][0], D[8][8][504]+505, INF);
	for(int i = 1; i <= H; i++) for(int j = 1; j <= W; j++) if('1' <= A[i][j] && A[i][j] <= '9') {
		int c = (A[i][j]&15) - 1;
		D[c][c][i][j] = 0;
	}
	for(int i = 0; i < N; i++) spread(D[i][i]);
	for(int l = 1; l < N; l++) {
		for(int s = 0, e = l; e < N; s++, e++) {
			for(int k = s; k < e; k++) {
				for(int i = 1; i <= H; i++) for(int j = 1; j <= W; j++) {
					int t = D[s][k][i][j] + D[k+1][e][i][j];
					if(t < D[s][e][i][j]) D[s][e][i][j] = t;
				}
			}
			spread(D[s][e]);
		}
	}
	for(int i = 1; i <= H; i++) for(int j = 1; j <= W; j++)
		if(D[0][N-1][i][j] < Ans) Ans = D[0][N-1][i][j];
	cout << (INF <= Ans ? -1 : Ans) << endl;
	return 0;
}

Compilation message

robots.cpp: In function 'void f(int, int, int)':
robots.cpp:44:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  if(ndr < 0) ndr = 3; if(3 < ndr) ndr = 0;
  ^~
robots.cpp:44:23: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  if(ndr < 0) ndr = 3; if(3 < ndr) ndr = 0;
                       ^~
robots.cpp: In function 'int main()':
robots.cpp:58:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &N, &W, &H);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
robots.cpp:59:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 1; i <= H; i++) scanf(" %s", A[i]+1);
                              ~~~~~^~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 87160 KB Output is correct
2 Correct 80 ms 87216 KB Output is correct
3 Correct 80 ms 87160 KB Output is correct
4 Correct 79 ms 87288 KB Output is correct
5 Correct 81 ms 87276 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 87160 KB Output is correct
2 Correct 80 ms 87216 KB Output is correct
3 Correct 80 ms 87160 KB Output is correct
4 Correct 79 ms 87288 KB Output is correct
5 Correct 81 ms 87276 KB Output is correct
6 Correct 78 ms 87160 KB Output is correct
7 Correct 79 ms 87168 KB Output is correct
8 Correct 78 ms 87160 KB Output is correct
9 Correct 79 ms 87180 KB Output is correct
10 Correct 78 ms 87288 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 87160 KB Output is correct
2 Correct 80 ms 87216 KB Output is correct
3 Correct 80 ms 87160 KB Output is correct
4 Correct 79 ms 87288 KB Output is correct
5 Correct 81 ms 87276 KB Output is correct
6 Correct 78 ms 87160 KB Output is correct
7 Correct 79 ms 87168 KB Output is correct
8 Correct 78 ms 87160 KB Output is correct
9 Correct 79 ms 87180 KB Output is correct
10 Correct 78 ms 87288 KB Output is correct
11 Correct 148 ms 92448 KB Output is correct
12 Correct 95 ms 92152 KB Output is correct
13 Correct 114 ms 92204 KB Output is correct
14 Correct 230 ms 93688 KB Output is correct
15 Correct 96 ms 92280 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 87160 KB Output is correct
2 Correct 80 ms 87216 KB Output is correct
3 Correct 80 ms 87160 KB Output is correct
4 Correct 79 ms 87288 KB Output is correct
5 Correct 81 ms 87276 KB Output is correct
6 Correct 78 ms 87160 KB Output is correct
7 Correct 79 ms 87168 KB Output is correct
8 Correct 78 ms 87160 KB Output is correct
9 Correct 79 ms 87180 KB Output is correct
10 Correct 78 ms 87288 KB Output is correct
11 Correct 148 ms 92448 KB Output is correct
12 Correct 95 ms 92152 KB Output is correct
13 Correct 114 ms 92204 KB Output is correct
14 Correct 230 ms 93688 KB Output is correct
15 Correct 96 ms 92280 KB Output is correct
16 Correct 201 ms 95688 KB Output is correct
17 Correct 592 ms 101172 KB Output is correct
18 Correct 129 ms 96632 KB Output is correct
19 Correct 191 ms 95628 KB Output is correct
20 Correct 373 ms 97528 KB Output is correct