oj.uz

Submission #122349

# Submission time Handle Problem Language Result Execution time Memory
122349 2019-06-28T05:24:28 Z 이온조(#2989) Robots (APIO13_robots) C++14
10 / 100
 7 ms 6400 KB 
#include <cstdio>
#include <algorithm>
#include <queue>
#include <tuple>
#include <set>
#pragma GCC optimize ("Ofast")
using namespace std;
using pii = pair<int, int>;

struct node {
	int x, y, s, e;
};

const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};

char A[509][509];
int D[501][501][10][10];
pii E[501][501][4];
bool vs[501][501][10][10];
vector<node> S[250009];

pii go(int x, int y, int dir) {
	int xx = x, yy = y, dd = dir;
	if(E[x][y][dir] != (pii){0, 0}) return E[x][y][dir];
	set<pii> chk;
	while(1) {
		if(chk.find({x, y}) != chk.end()) {
			puts("CYCLE");
			exit(0);
		}
		chk.insert({x, y});
		// printf("in go:  x: %d, y: %d, dir: %d\n", x, y, dir);
		if(A[x][y] == 'A') dir += 3, dir %= 4;
		if(A[x][y] == 'C') dir += 1, dir %= 4;
		int X = x + dx[dir], Y = y + dy[dir];
		if(A[X][Y] == 'x') break;
		x = X; y = Y;
	}
	// puts("done");
	return E[xx][yy][dd] = {x, y};
}

inline void mark(node X, int dist) {
	int a = X.x, b = X.y, c = X.s, d = X.e;
	vs[a][b][c][d] = 1; D[a][b][c][d] = dist;
}

int main() {
	int N, W, H; scanf("%d%d%d",&N,&W,&H);
	for(int i=0; i<=H+1; i++) for(int j=0; j<=W+1; j++) A[i][j] = 'x';
	for(int i=1; i<=H; i++) {
		for(int j=1; j<=W; j++) {
			scanf(" %c", &A[i][j]);
			if('1' <= A[i][j] && A[i][j] <= '9') {
				int id = A[i][j] - '0';
				S[0].push_back({i, j, id, id});
			}
		}
	}
	int sum = 0;
	queue<node> que;
	for(int i=1; i<=N; i++) {
		int c = 0;
		do {
			for(auto& it: S[c]) if(!vs[it.x][it.y][it.s][it.e] && it.e - it.s + 1 == i) {
				que.push(it);
				mark(it, sum + c);
			}
			while(S[c].size()) S[c].pop_back();
			int sz = que.size();
			while(sz--) {
				node P = que.front(); que.pop();
				// printf("i: %d, dist: %d, x: %d, y: %d, s: %d, e: %d\n", i, sum + c, P.x, P.y, P.s, P.e);
				for(int k=0; k<4; k++) {
					int X, Y; tie(X, Y) = go(P.x, P.y, k);
					// printf("X: %d, Y: %d\n", X, Y);
					if(!vs[X][Y][P.s][P.e]) {
						que.push({X, Y, P.s, P.e});
						mark({X, Y, P.s, P.e}, sum + c + 1);
					}
				}
			}
			++c;
		} while(que.size());

		if(i == N) break;
		// puts("CALCULATE START");
		int gmn = 1e9;
		for(int p=1; p<=H; p++) {
			for(int q=1; q<=W; q++) {
				for(int j=i+1; j<=N; j++) {
					for(int k=j-i; k<j; k++) {
						if(vs[p][q][j-i][k] && vs[p][q][k+1][j]) {
							gmn = min(gmn, D[p][q][j-i][k] + D[p][q][k+1][j]);
						}
					}
				}
			}
		}
		for(int p=1; p<=H; p++) {
			for(int q=1; q<=W; q++) {
				for(int j=i+1; j<=N; j++) {
					int mn = 1e9;
					for(int k=j-i; k<j; k++) {
						if(vs[p][q][j-i][k] && vs[p][q][k+1][j]) {
							mn = min(mn, D[p][q][j-i][k] + D[p][q][k+1][j]);
						}
					}
					if(mn != 1e9) S[mn - gmn].push_back({p, q, j-i, j});
				}
			}
		}
		sum = gmn;
		if(sum == 1e9) break;
	}
	if(sum == 1e9) puts("-1");
	else printf("%d", sum);
	return 0;
}

Compilation message

robots.cpp: In function 'int main()':
robots.cpp:50:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int N, W, H; scanf("%d%d%d",&N,&W,&H);
               ~~~~~^~~~~~~~~~~~~~~~~~~
robots.cpp:54:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf(" %c", &A[i][j]);
    ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6144 KB Output is correct
2 Correct 7 ms 6144 KB Output is correct
3 Correct 6 ms 6144 KB Output is correct
4 Correct 7 ms 6272 KB Output is correct
5 Correct 7 ms 6400 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6144 KB Output is correct
2 Correct 7 ms 6144 KB Output is correct
3 Correct 6 ms 6144 KB Output is correct
4 Correct 7 ms 6272 KB Output is correct
5 Correct 7 ms 6400 KB Output is correct
6 Correct 7 ms 6272 KB Output is correct
7 Correct 6 ms 6272 KB Output is correct
8 Correct 6 ms 6272 KB Output is correct
9 Incorrect 7 ms 6272 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6144 KB Output is correct
2 Correct 7 ms 6144 KB Output is correct
3 Correct 6 ms 6144 KB Output is correct
4 Correct 7 ms 6272 KB Output is correct
5 Correct 7 ms 6400 KB Output is correct
6 Correct 7 ms 6272 KB Output is correct
7 Correct 6 ms 6272 KB Output is correct
8 Correct 6 ms 6272 KB Output is correct
9 Incorrect 7 ms 6272 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6144 KB Output is correct
2 Correct 7 ms 6144 KB Output is correct
3 Correct 6 ms 6144 KB Output is correct
4 Correct 7 ms 6272 KB Output is correct
5 Correct 7 ms 6400 KB Output is correct
6 Correct 7 ms 6272 KB Output is correct
7 Correct 6 ms 6272 KB Output is correct
8 Correct 6 ms 6272 KB Output is correct
9 Incorrect 7 ms 6272 KB Output isn't correct
10 Halted 0 ms 0 KB -