Submission #1276913

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276913		g4yuhg	Robots (APIO13_robots)	C++20	100 / 100	309 ms	88132 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 * 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) {
	if (thuoc[i][j]) return;
	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[10][10], k;

ll d[500 * 500 + 1][46];
bool vis[500 * 500 + 1][46];

pii ptich[50];

vector<pii> p[N * N];

void dij() {
	queue<pii> q;
	for (int i = 1; i <= cur; i ++) {
		for (int j = 1; j <= k; j ++) {
			d[i][j] = inf;
		}
	}
	for (int i = 1; i <= n; i ++) {
		q.push({idx[bdau[i].fi][bdau[i].se], ax[i][i]});
		vis[idx[bdau[i].fi][bdau[i].se]][ax[i][i]] = 1;
		d[idx[bdau[i].fi][bdau[i].se]][ax[i][i]] = 0;
	}
	// lam tung len
	for (int len = 1; len <= n; len ++) {
		//cout << "len " << len << " " << q.size() << endl;
		if (len == 1) {
			while (q.size()) {
				auto u = q.front();
				q.pop();
				//cout << " " << d[u.fi][u.se] << " xy " << dinh[u.fi].fi << " " << dinh[u.fi].se << " | " << ptich[u.se].fi << " " << ptich[u.se].se << endl;
				for (auto v : adj[u.fi]) {
					if (d[v][u.se] > d[u.fi][u.se] + 1) {
						d[v][u.se] = d[u.fi][u.se] + 1;
						q.push({v, u.se});
					}
				}
			}
			continue;
		}
		ll mn = inf;
		for (int u = 1; u <= cur; u ++) {
			for (int i = 1; i <= n; i ++) {
				ll j = i + len - 1;
				if (j > n) break;
				for (int mid = i; mid < j; mid ++) {
					d[u][ax[i][j]] = min(d[u][ax[i][j]], d[u][ax[i][mid]] + d[u][ax[mid + 1][j]]);
				}
				mn = min(mn, d[u][ax[i][j]]);
				if (d[u][ax[i][j]] != inf) {
					p[d[u][ax[i][j]]].push_back({u, ax[i][j]});
					//cout << " push " << d[u][ax[i][j]] << " | " << dinh[u].fi << " " << dinh[u].se << " | " << i << " " << j << endl; 
				}
			}
		}
		if (mn == inf) {
			//cout << " cut" << endl;
			continue;
		}
		for (auto it : p[mn]) {
			q.push(it);
			vis[it.fi][it.se] = 1;
		}
		while (q.size()) {
			auto u = q.front();
			q.pop();
			//cout << " " << d[u.fi][u.se] << " xy " << dinh[u.fi].fi << " " << dinh[u.fi].se << " | " << ptich[u.se].fi << " " << ptich[u.se].se << endl;
			ll c = d[u.fi][u.se];
			for (auto it : p[c + 1]) {
				if (d[it.fi][it.se] < c + 1) continue;
				q.push({it.fi, it.se});
			}
			p[c + 1].clear();
			for (auto v : adj[u.fi]) {
				if (d[v][u.se] > c + 1) {
					d[v][u.se] = c + 1;
					q.push({v, u.se});
					vis[v][u.se] = 1;
				}
			}
		}
	}
}

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);
	}
	
	for (int i = 1; i <= n; i ++) {
		for (int j = i; j <= n; j ++) {
			ax[i][j] = ++ k;
			ptich[k] = {i, j};
		}
	}
	
	dij();
	
	for (int u = 1; u <= cur; u ++) {
		ans = min(ans, d[u][ax[1][n]]);
	}
	
	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: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40