Submission #1276848

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276848		g4yuhg	Robots (APIO13_robots)	C++20	10 / 100	1 ms	580 KiB

robots

//Huyduocdithitp
#include<bits/stdc++.h>
typedef int ll;
#define endl '\n'
#define fi first
#define se second
#define pii pair<ll, ll>
#define N 505
using namespace std;

ll getbit(ll mask, ll i) {
	return (mask >> i) & 1;
}

ll onbit(ll mask, ll i){
	return mask | (1 << i);
}

const ll inf = 1e9;

const ll hx[] = {-1, 0, 1, 0}; // len phai xuong trai
const ll hy[] = {0, 1, 0, -1};

bool ghuy4g;

ll n, w, h, ans = inf;

char a[N][N];

bool is[N][N][4];
ll vst[N][N][4];

pii nxt[N][N][4];

vector<ll> adj[N];

ll luot = 0;

bool isthem[N][N];

queue<pii> q;

pii dfs(ll i, ll j, ll t) {
	////cout << i << " " << j << " " << t << endl;
	vst[i][j][t] = luot;
	ll ii, jj, tt;
	if (a[i][j] == 'A') {
		tt = t - 1;
		if (tt < 0) tt = 3;
		ii = i + hx[tt];
		jj = j + hy[tt];
	}
	else if (a[i][j] == 'C') {
		tt = t + 1;
		if (tt == 4) tt = 0;
		ii = i + hx[tt];
		jj = j + hy[tt];
	}
	else {
		ii = i + hx[t];
		jj = j + hy[t];
		tt = t;
	}
	
	if (ii < 1 || ii > h || jj < 1 || jj > w || a[ii][jj] == 'x') {
		////cout << "chan roi " << endl;
		if (isthem[i][j] == 0){
			isthem[i][j] = 1;
			q.push({i, j});
		}
		return nxt[i][j][t] = {i, j};
	}
	if (vst[ii][jj][tt] == luot) {
		return nxt[i][j][t] = {-1, -1};
	}
	else if (vst[ii][jj][tt] > 0 && vst[ii][jj][tt] != luot) {
		return nxt[i][j][t] = dfs(ii, jj, tt);
	}
	else {
		return nxt[i][j][t] = dfs(ii, jj, tt);
	}
	
	vst[i][j][t] = luot;
}

pii bdau[10];

ll idx[N][N]; // idx cua dinh i j
pii dinh[N * N];

ll cur = 0;

bool thuoc[N][N];

void dfs2(ll i, ll j) {
	cur ++ ;
	idx[i][j] = cur;
	dinh[cur] = {i, j};
	thuoc[i][j] = 1;
	for (int z = 0; z < 4; z ++) {
		pii moi = nxt[i][j][z];
		if (moi.fi != 0 && moi.fi != -1) {
			if (thuoc[moi.fi][moi.se] == 0) {
				dfs2(moi.fi, moi.se);
			}
		}
		if (moi.fi != i || moi.se != j) {
			adj[idx[i][j]].push_back({idx[moi.fi][moi.se]});
		}
	}
}

ll ax[N]; // ax[mask] la mask 000101..1001 co chi so la bao nhieu
ll ax1[N]; // ax[k] = mask
ll k;

ll check(ll mask1, ll mask2) {
	ll mask = (mask1 & mask2);
	if (mask != 0) { // co bit chung
		return 0;
	}
	mask = (mask1 ^ mask2);
	bool flag = 1;
	ll sd = 0;
	for (int i = 1; i <= n; i ++) {
		if (getbit(mask, i - 1) == 0) continue;
		ll j = i;
		while (j <= n && getbit(mask, j - 1) == 1) {
			j ++ ;
		}
		i = j - 1;
		sd ++ ;
	}
	if (sd > 1) {
		flag = 0;
	}
	if (flag == 0) return 0;
	return ax[mask];
}

void dij() {
	vector<vector<ll>> d(cur + 1, vector<ll>(k + 1));
	for (int i = 1; i <= cur; i ++) {
		for (int j = 1; j <= k; j ++) {
			d[i][j] = inf;
		}
	}
	priority_queue<pair<ll, pii>, vector<pair<ll, pii>>, greater<pair<ll, pii>>> pq;
	for (int i = 1; i <= n; i ++) {
		ll x = bdau[i].fi, y = bdau[i].se, mask = onbit(0, i - 1), id = ax[mask];
		ll u = idx[x][y];
		d[u][id] = 0;
		pq.push({d[u][id], {u, id}});
	}
	while (pq.size()) {
		auto c = pq.top().fi;
		auto u = pq.top().se;
		pq.pop();
		if (c > d[u.fi][u.se]) continue;
		//cout << endl;
		if (__builtin_popcount(ax1[u.se]) == n) {
			ans = min(ans, c);
		}
		ll mask = ax1[u.se];
		for (int i = 1; i <= k; i ++) {
			if (i == u.se) continue;
			if (d[u.fi][i] == inf) continue;
			ll mask2 = ax1[i];
			ll newid = check(mask, mask2);
			if (newid > 0 && d[u.fi][newid] > d[u.fi][u.se] + d[u.fi][i]) {
				d[u.fi][newid] = d[u.fi][u.se] + d[u.fi][i];
				pq.push({d[u.fi][newid], {u.fi, newid}});
			}
		}
		for (auto v : adj[u.fi]) {
			if (d[v][u.se] > c + 1) {
				d[v][u.se] = c + 1;
				pq.push({d[v][u.se], {v, u.se}});
			}
		}
	}
}

void pre() {
	/*for (int i = 1; i <= n; i ++) {
		for (int z = 0; z < 4; z ++) {
			++ luot;
			dfs(bdau[i].fi, bdau[i].se, z);
		}
	}*/
	
	for (int i = 1; i <= n; i ++) {
		q.push({bdau[i].fi, bdau[i].se});
	}
	
	while (q.size()) {
		auto u = q.front();
		q.pop();
		for (int z = 0; z < 4; z ++) {
			if (vst[u.fi][u.se][z] > 0) continue;
			++ luot;
			dfs(u.fi, u.se, z);
		}
	}
	
	////cout << nxt[1][1][0].fi << " " << nxt[1][1][0].se << endl;;
	////cout << nxt[1][1][1].fi << " " << nxt[1][1][1].se << endl;;
	////cout << nxt[1][1][2].fi << " " << nxt[1][1][2].se << endl;;
	
	for (int i = 1; i <= n; i ++) {
		dfs2(bdau[i].fi, bdau[i].se);
	}
	
	//cout << "cur " << cur << endl;
	//cout << nxt[5][5][1].fi << " " << nxt[5][5][1].se << endl;
	for (int mask = 0; mask < (1 << n); mask ++) {
		bool flag = 1;
		ll sd = 0;
		for (int i = 1; i <= n; i ++) {
			if (getbit(mask, i - 1) == 0) continue;
			ll j = i;
			while (j <= n && getbit(mask, j - 1) == 1) {
				j ++ ;
			}
			i = j - 1;
			sd ++ ;
		}
		if (sd > 1) {
			flag = 0;
		}
		if (flag) {
			k ++ ;
			ax[mask] = k;
			ax1[k] = mask;
		}
	}
	
	dij();
	
	if (ans == inf) {
		cout << -1;
	}
	else {
		cout << ans;
	}
}

bool klinh;

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> w >> h;
	for (int i = 1; i <= h; i ++) {
		for (int j = 1; j <= w; j ++) {
			cin >> a[i][j];
			if ('1' <= a[i][j] && a[i][j] <= '9') {
				bdau[a[i][j] - '0'] = {i, j};
			}
		}
	}
	pre();
	
	cerr << fabs(&klinh - &ghuy4g) / double(1024 * 1024);
	
	return 0;
}

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