Submission #122448

#	Time	Username	Problem	Language	Result	Execution time	Memory
122448		onjo0127	Robots (APIO13_robots)	C++11	100 / 100	1200 ms	125136 KiB

robots

#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;
};
 
node QUE[250009];
 
struct QUEUE {
	const int siz = 250000;
	int h = 0, t = 0;
	void push(node X) {QUE[h++] = X; if(h == siz) h = 0;}
	void pop() {
		t++;
		if(t == siz) t = 0;
	}
	node front() {
		return QUE[t];
	}
	int sz() {
		if(h >= t) return h - t;
		else return siz - t + h;
	}
};
 
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};
const int INF = 1e9;
 
char A[509][509];
int D[10][10][501][501];
char I[10][10][501][501];
pii E[4][501][501];
bool vs[10][10][501][501], chk[501][501];
vector<node> S[250009];
 
pii go(int x, int y, int dir) {
	int xx = x, yy = y, dd = dir;
	if(E[dir][x][y] != (pii){0, 0}) return E[dir][x][y];
	E[dir][x][y] = {-1, -1};
	// printf("in go:  x: %d, y: %d, dir: %d\n", x, y, dir);
	if(A[x][y] == 'A') dir += 3, dir = (dir & 3);
	if(A[x][y] == 'C') dir += 1, dir = (dir & 3);
	int X = x + dx[dir], Y = y + dy[dir];
	if(A[X][Y] == 'x') {return E[dd][xx][yy] = {x, y};}
	return E[dd][x][y] = go(X, Y, dir);
}
 
inline void mark(node X, int dist) {
	int a = X.x, b = X.y, c = X.s, d = X.e;
	vs[c][d][a][b] = 1; D[c][d][a][b] = 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++) scanf(" %s", A[i]+1);
	for(int i=1; i<=H; i++) {
		for(int j=1; j<=W; j++) {
			if('1' <= A[i][j] && A[i][j] <= '9') {
				int id = A[i][j] - '0';
				S[0].push_back({i, j, id, id});
			}
		}
		A[i][W+1] = 'x';
	}
	int sum = 0;
	QUEUE que;
	for(int i=1; i<=N; i++) {
		for(int p=1; p<=H; p++) for(int q=1; q<=W; q++) chk[p][q] = 0;
		int c = 0;
		do {
			for(auto& it: S[c]) if(!vs[it.s][it.e][it.x][it.y] && it.e - it.s + 1 == i) {
				que.push(it);
				mark(it, sum + c);
			}
			while(S[c].size()) S[c].pop_back();
			int sz = que.sz();
			while(sz--) {
				node P = que.front(); que.pop();
				chk[P.x][P.y] = 1;
				// 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[P.s][P.e][X][Y] && X != -1) {
						que.push({X, Y, P.s, P.e});
						mark({X, Y, P.s, P.e}, sum + c + 1);
					}
				}
			}
			++c;
		} while(que.sz());
 
		if(i == N) break;
		// puts("CALCULATE START");
		int gmn = INF, t, p, q, j, k, s, e, mn, v;
		for(t=1; t<=2; t++) {
			for(p=1; p<=H; p++) {
				for(q=1; q<=W; q++) {
					if(!chk[p][q]) continue;
					for(j=i+1; j<=N; j++) {
						s = j-i, e = j-1, mn = INF;
						if(i != 1) s = I[j-i][j-1][p][q], e = I[j-i+1][j][p][q];
						I[j-i][j][p][q] = j-i;
						for(k=s; k<=e+1; k++) {
							v = D[j-i][k][p][q] + D[k+1][j][p][q];
							if(vs[j-i][k][p][q] && vs[k+1][j][p][q] && mn > v) {
								mn = v;
								I[j-i][j][p][q] = k;
							}
						}
						if(t == 1) gmn = min(gmn, mn);
						if(t == 2 && mn != INF) S[mn - gmn].push_back({p, q, j-i, j});
					}
				}
			}
		}
		sum = gmn;
		if(sum == INF) break;
	}
	if(sum == INF) puts("-1");
	else printf("%d", sum);
	return 0;
}

Compilation message (stderr)

robots.cpp: In function 'int main()':
robots.cpp:62: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:64:31: 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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40