Submission #1232428

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232428		kaiboy	Portals (BOI14_portals)	C++20	100 / 100	257 ms	28884 KiB

portals

#include <algorithm>
#include <iostream>

using namespace std;

const int    N = 1000;
const int    M = 1000;
const int  INF = 0x3f3f3f3f;
const int DI[] = { 0, 0, -1, 1 };
const int DJ[] = { -1, 1, 0, 0 };

char aa[N][M + 1];
int dd_[N][N], ee[N][N][4], dd[N][N];
int pq[N * N], iq[N * N + 1], cnt, m;

bool lt(int i, int j) {
	return dd[i / m][i % m] < dd[j / m][j % m];
}

int p2(int p) {
	return (p <<= 1) > cnt ? 0 : p + lt(iq[p ^ 1], iq[p]);
}

void pq_up(int i) {
	int p = pq[i];
	for (int j, q; (q = p >> 1) && lt(i, j = iq[q]); p = q)
		iq[pq[j] = p] = j;
	iq[pq[i] = p] = i;
}

void pq_dn(int i) {
	int p = pq[i];
	for (int j, q; (q = p2(p)) && lt(j = iq[q], i); p = q)
		iq[pq[j] = p] = j;
	iq[pq[i] = p] = i;
}

void pq_add_last(int i) {
	iq[pq[i] = ++cnt] = i;
}

int pq_remove_first() {
	int i = iq[1], j = iq[cnt--];
	if (i != j)
		pq[j] = 1, pq_dn(j);
	pq[i] = 0;
	return i;
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	int n; cin >> n >> m;
	for (int i = 0; i < n; i++)
		cin >> aa[i];
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			dd_[i][j] = aa[i][j] == '#' ? 0 : i == 0 || i == n - 1 || j == 0 || j == m - 1 ? 1 : INF;
	for (int i = 0; i < n; i++) {
		for (int j = 1; j < m; j++)
			dd_[i][j] = min(dd_[i][j], dd_[i][j - 1] + 1);
		for (int j = m - 2; j >= 0; j--)
			dd_[i][j] = min(dd_[i][j], dd_[i][j + 1] + 1);
	}
	for (int j = 0; j < m; j++) {
		for (int i = 1; i < n; i++)
			dd_[i][j] = min(dd_[i][j], dd_[i - 1][j] + 1);
		for (int i = n - 2; i >= 0; i--)
			dd_[i][j] = min(dd_[i][j], dd_[i + 1][j] + 1);
	}
	for (int i = 0; i < n; i++) {
		for (int d = 0, j = 0; j < m; j++)
			ee[i][j][0] = d = aa[i][j] == '#' ? 0 : d + 1;
		for (int d = 0, j = m - 1; j >= 0; j--)
			ee[i][j][1] = d = aa[i][j] == '#' ? 0 : d + 1;
	}
	for (int j = 0; j < m; j++) {
		for (int d = 0, i = 0; i < n; i++)
			ee[i][j][2] = d = aa[i][j] == '#' ? 0 : d + 1;
		for (int d = 0, i = n - 1; i >= 0; i--)
			ee[i][j][3] = d = aa[i][j] == '#' ? 0 : d + 1;
	}
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			if (aa[i][j] == 'S')
				pq_add_last(i * m + j);
			else
				dd[i][j] = INF;
	while (cnt) {
		int ij = pq_remove_first(), i = ij / m, j = ij % m, d = dd[i][j];
		if (aa[i][j] == 'C') {
			cout << d << '\n';
			return 0;
		}
		for (int h = 0; h < 4; h++) {
			int i_ = i + DI[h], j_ = j + DJ[h], ij_ = i_ * m + j_, d_ = d + 1;
			if (0 <= i_ && i_ < n && 0 <= j_ && j_ < m && aa[i_][j_] != '#' && dd[i_][j_] > d_) {
				if (dd[i_][j_] == INF)
					pq_add_last(ij_);
				dd[i_][j_] = d_, pq_up(ij_);
			}
			int e = ee[i][j][h] - 1;
			i_ = i + DI[h] * e, j_ = j + DJ[h] * e, ij_ = i_ * m + j_, d_ = d + dd_[i][j];
			if (dd[i_][j_] > d_) {
				if (dd[i_][j_] == INF)
					pq_add_last(ij_);
				dd[i_][j_] = d_, pq_up(ij_);
			}
		}
	}
	return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 19 / 19
• Subtask 5: 30 / 30