oj.uz

Submission #287772

# Submission time Handle Problem Language Result Execution time Memory
287772 2020-08-31T23:50:32 Z Namnamseo Robots (APIO13_robots) C++17
0 / 100
 35 ms 57464 KB 
#include <cstdio>
#include <cstring>
#include <utility>
#include <functional>
#include <vector>
#include <queue>
#define rep(i,n) for(int i=0;i<n;++i)
#define rrep(i,n) for(int i=1;i<=n;++i)
#define x first
#define y second
#define eb emplace_back
using namespace std;
using pp=pair<int,int>;
int n, m, k;
char q[510][510];
pp e[510][510][4];
pp il[10];

using t4=tuple<int,int,int,int>;

int dp[510][510][50];
bool iq[510][510][50];

vector<pp> rm[510][510];

const int dx[5] = {0, 1, 0, -1}, *dy = dx+1;
pp E(int x, int y, int d) {
	pp &ret = e[x][y][d];
	if (ret.x) return ret;
	int nx=x+dx[d], ny=y+dy[d];
	if (1<=nx && nx<=n && 1<=ny && ny<=m && q[nx][ny]!='x') {
		switch(q[nx][ny]) {
			case 'A': ret = E(nx, ny, (d+3)%4); break;
			case 'C': ret = E(nx, ny, (d+1)%4); break;
			default: ret = E(nx, ny, d); break;
		}
		return ret;
	} else return ret={x, y};
}

int C[10][10];

queue<t4> Q[10];

int main()
{
	scanf("%d%d%d",&k,&m,&n);
	rrep(i, n) {
		scanf("%s", q[i]+1);
		rrep(j, m) if ((q[i][j]&48)==48) il[q[i][j]-48]={i,j};
	}

	{ static int p = 0; rrep(i, k) rrep(j, i) C[j][i] = ++p; }

	memset(dp,0x3f,sizeof(dp));
	rrep(i, k) {
		Q[1].emplace(il[i].x, il[i].y, i, i);
		dp[il[i].x][il[i].y][C[i][i]] = 0;
		iq[il[i].x][il[i].y][C[i][i]] = 1;
	}

	rrep(len, k) {
		while(Q[len].size()) {
			int x,y,l,r;
			tie(x,y,l,r) = Q[len].front(); Q[len].pop();
			int p = C[l][r];
			rep(d, 4) {
				pp t = E(x, y, d);
				if (t == pp(x, y)) continue;
				if (dp[t.x][t.y][p] > dp[x][y][p]+1) {
					dp[t.x][t.y][p] = dp[x][y][p]+1;
					if (!iq[t.x][t.y][p]) {
						iq[t.x][t.y][p] = 1;
						Q[len].emplace(t.x, t.y, l, r);
					}
				}
			}
			auto R = [&](int l, int r, int v) {
				int np = C[l][r];
				if (dp[x][y][np] > v) {
					dp[x][y][np] = v;
					if (!iq[x][y][np]) iq[x][y][np]=1,
						Q[r-l+1].emplace(x, y, l, r);
				}
			};
			for(int i=1; i<l; ++i) if ((l-i) <= (r-l+1))
				R(i, r,
				dp[x][y][C[i][l-1]] + dp[x][y][p]);
			for(int i=r+1; i<=k; ++i) if ((i-r) < (r-l+1))
				R(l, i,
				dp[x][y][C[r+1][i]] + dp[x][y][p]);
		}
	}

	int ans = 2e9;
	rrep(i, n) rrep(j, m)
		ans = min(ans, dp[i][j][C[1][k]]);

	if (ans == int(2e9)) ans = -1;

	printf("%d\n", ans);

	return 0;
}

Compilation message

robots.cpp: In function 'int main()':
robots.cpp:47:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   47 |  scanf("%d%d%d",&k,&m,&n);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~
robots.cpp:49:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   49 |   scanf("%s", q[i]+1);
      |   ~~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 57464 KB Output is correct
2 Incorrect 35 ms 57344 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 57464 KB Output is correct
2 Incorrect 35 ms 57344 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 57464 KB Output is correct
2 Incorrect 35 ms 57344 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 57464 KB Output is correct
2 Incorrect 35 ms 57344 KB Output isn't correct
3 Halted 0 ms 0 KB -