oj.uz

Submission #124202

# Submission time Handle Problem Language Result Execution time Memory
124202 2019-07-02T16:09:00 Z youngyojun Robots (APIO13_robots) C++11
100 / 100
 528 ms 101184 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 90 ms 87132 KB Output is correct
2 Correct 78 ms 87160 KB Output is correct
3 Correct 75 ms 87160 KB Output is correct
4 Correct 76 ms 87264 KB Output is correct
5 Correct 75 ms 87288 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 87132 KB Output is correct
2 Correct 78 ms 87160 KB Output is correct
3 Correct 75 ms 87160 KB Output is correct
4 Correct 76 ms 87264 KB Output is correct
5 Correct 75 ms 87288 KB Output is correct
6 Correct 76 ms 87160 KB Output is correct
7 Correct 84 ms 87200 KB Output is correct
8 Correct 77 ms 87160 KB Output is correct
9 Correct 76 ms 87260 KB Output is correct
10 Correct 75 ms 87288 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 87132 KB Output is correct
2 Correct 78 ms 87160 KB Output is correct
3 Correct 75 ms 87160 KB Output is correct
4 Correct 76 ms 87264 KB Output is correct
5 Correct 75 ms 87288 KB Output is correct
6 Correct 76 ms 87160 KB Output is correct
7 Correct 84 ms 87200 KB Output is correct
8 Correct 77 ms 87160 KB Output is correct
9 Correct 76 ms 87260 KB Output is correct
10 Correct 75 ms 87288 KB Output is correct
11 Correct 141 ms 92556 KB Output is correct
12 Correct 86 ms 92084 KB Output is correct
13 Correct 101 ms 92152 KB Output is correct
14 Correct 214 ms 93816 KB Output is correct
15 Correct 91 ms 92304 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 87132 KB Output is correct
2 Correct 78 ms 87160 KB Output is correct
3 Correct 75 ms 87160 KB Output is correct
4 Correct 76 ms 87264 KB Output is correct
5 Correct 75 ms 87288 KB Output is correct
6 Correct 76 ms 87160 KB Output is correct
7 Correct 84 ms 87200 KB Output is correct
8 Correct 77 ms 87160 KB Output is correct
9 Correct 76 ms 87260 KB Output is correct
10 Correct 75 ms 87288 KB Output is correct
11 Correct 141 ms 92556 KB Output is correct
12 Correct 86 ms 92084 KB Output is correct
13 Correct 101 ms 92152 KB Output is correct
14 Correct 214 ms 93816 KB Output is correct
15 Correct 91 ms 92304 KB Output is correct
16 Correct 187 ms 95824 KB Output is correct
17 Correct 528 ms 101184 KB Output is correct
18 Correct 122 ms 96504 KB Output is correct
19 Correct 178 ms 95608 KB Output is correct
20 Correct 368 ms 97576 KB Output is correct