Submission #899249

#	Time	Username	Problem	Language	Result	Execution time	Memory
899249		Tob	Robots (APIO13_robots)	C++14	100 / 100	659 ms	139860 KiB

robots

#include <bits/stdc++.h>

#define ll long long
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

typedef pair <ll, ll> pii;

const int G = 10, H = 507, inf = 0x3f3f3f3f;
const int N = H*H;

int n, g, h, w;
char mat[H][H];
int red[H][H], adj[N][4], po[G], bio[G][N], dp[N][G][G];

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

int En(int x, int y) {return (x-1)*w+y;}
int Rot(int sm, int ad) {return (sm+4+ad)%4;}
int Build(int x, int y, int o) {
	int z = En(x,y), rd = Rot(o, red[x][y]);
	if (adj[z][o]) return adj[z][o];
	int nx = x + dx[rd], ny = y + dy[rd];
	if (mat[nx][ny] == 'x') return adj[z][o] = z;
	return adj[z][o] = Build(nx, ny, rd);
}

void bfs(int a, int x) {
	memset(bio[a], inf, sizeof bio[a]);
	bio[a][x] = 0;
	queue <int> q;
	q.push(x);
	while (!q.empty()) {
		int px = q.front();
		q.pop();
		for (int i = 0; i < 4; i++) {
			int y = adj[px][i];
			if (y == -1 || bio[a][y] != inf) continue;
			bio[a][y] = bio[a][px] + 1;
			q.push(y);
		}
	}
}

bool did[N];
vector <int> td[N];
struct Q {
	int mn = 0;
	int Get() {
		while (mn < N && (td[mn].empty() || did[td[mn].back()])) {
			if (td[mn].empty()) mn++;
			else td[mn].pop_back();
		}
		if (mn == N) return 0;
		int x = td[mn].back();
		did[x] = 1;
		return x;
	}
	void Push(int x, int y) {td[x].pb(y);}
	void Clear() {
		memset(did, 0, sizeof did);
		for (int i = 0; i < N; i++) td[i].clear();
		mn = 0;
	}
};

void dij(int a, int b) {
	Q q;
	for (int i = 1; i <= n; i++) if (dp[i][a][b] != inf) q.Push(dp[i][a][b], i);
	for (int x = q.Get(); x; x = q.Get()) {
		for (int i = 0; i < 4; i++) {
			int y = adj[x][i];
			if (y == -1) continue;
			int d1 = dp[x][a][b], d2 = dp[y][a][b];
			if (d1+1 < d2) {
				q.Push(d1+1, y);
				dp[y][a][b] = d1+1;
			}
		}
	}
	q.Clear();
}

int main () {
//	FIO;
	cin >> g >> w >> h;
	
	for (int i = 0; i <= h+1; i++) mat[i][0] = mat[i][w+1] = 'x';
	for (int i = 0; i <= w+1; i++) mat[0][i] = mat[h+1][i] = 'x';
	for (int i = 1; i <= h; i++) {
		for (int j = 1; j <= w; j++) {
			cin >> mat[i][j];
			if (mat[i][j] >= '0' && mat[i][j] <= '9') {
				po[mat[i][j]-'0'] = En(i,j);
			}
			else if (mat[i][j] == 'A') red[i][j] = -1;
			else if (mat[i][j] == 'C') red[i][j] = 1;
		}
	}
	
	for (int i = 1; i <= h; i++) {
		for (int j = 1; j <= w; j++) {
			if (mat[i][j] != 'x') for (int k = 0; k < 4; k++) Build(i, j, k);
		}
	}
	n = w*h;
	memset(dp, inf, sizeof dp);
	
	for (int i = 1; i <= g; i++) {
		bfs(i, po[i]);
		for (int j = 1; j <= n; j++) dp[j][i][i] = bio[i][j];
	}
	
	for (int i = 2; i <= g; i++) {
		for (int j = 1; j <= g-i+1; j++) {
			for (int i1 = 1; i1 <= n; i1++) {
				for (int k = 1; k < i; k++) {
					dp[i1][j][j+i-1] = min(dp[i1][j][j+i-1], dp[i1][j][j+k-1] + dp[i1][j+k][j+i-1]);
				}
			}
			dij(j, j+i-1);
		}
	}
	
	int mn = inf;
	for (int i = 1; i <= n; i++) {
		mn = min(mn, dp[i][1][g]);
	}
	
	if (mn == inf) cout << -1;
	else cout << mn;

	return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40