Submission #555346

#	Time	Username	Problem	Language	Result	Execution time	Memory
555346		sidon	Portals (BOI14_portals)	C++17	100 / 100	669 ms	108424 KiB

portals

#include <bits/stdc++.h>
using namespace std;

const int INF = 2e9;

const array<int, 2> dd[4] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int n, m, o[2]; cin >> n >> m;

	string a[n]; for(auto &i : a) cin >> i;

	vector<array<int, 2>> g[n*m];
	queue<int> q;
	int d[n*m];
	fill(d, d + n*m, INF);

	for(int i {}, u {}; i < n; ++i) {
		for(int j {}; j < m; ++j, ++u) {
			if(a[i][j] == 'S') o[0] = u, a[i][j] = '.';
			if(a[i][j] == 'C') o[1] = u, a[i][j] = '.';
			if(a[i][j] == '.') {
				if(i && a[i-1][j] == '.') {
					g[u-m].push_back({u, 1});
					g[u].push_back({u-m, 1});
				}
				if(j && a[i][j-1] == '.') {
					g[u-1].push_back({u, 1});
					g[u].push_back({u-1, 1});
				}
				bool ok {};
				for(auto [dx, dy] : dd) {
					int x = i + dx, y = j + dy;
					if(min(x, y) < 0 || x == n || y == m || a[x][y] == '#') ok = 1;
				}
				if(ok) q.push(u), d[u] = 0;
			}
		}
	}

	while(!empty(q)) {
		int u = q.front(); q.pop();
		for(auto [v, w] : g[u]) if(d[v] == INF) {
			d[v] = d[u] + 1;
			q.push(v);
		}
	}

	for(int i {}, u {}; i < n; ++i) {
		int last = u = i * m;
		for(int j {}; j < m; ++j, ++u) if(a[i][j] == '.') {
			if(j && a[i][j-1] != '.') last = u;
			else
				g[u].push_back({last, d[u] + 1});
		}
		last = u = i * m + m - 1;
		for(int j = m; j--; --u) if(a[i][j] == '.') {
			if(j + 1 < m && a[i][j+1] != '.') last = u;
			else
				g[u].push_back({last, d[u] + 1});
		}
	}

	for(int j {}, u {}; j < m; ++j) {
		int last = u = j;
		for(int i {}; i < n; ++i, u += m) if(a[i][j] == '.') {
			if(i && a[i-1][j] != '.') last = u;
			else
				g[u].push_back({last, d[u] + 1});
		}
		last = u = (n - 1) * m + j;
		for(int i = n; i--; u -= m) if(a[i][j] == '.') {
			if(i + 1 < n && a[i+1][j] != '.') last = u;
			else
				g[u].push_back({last, d[u] + 1});
		}
	}

	fill(d, d + n*m, INF);
	priority_queue<pair<int, int>> pq;
	pq.emplace(d[o[0]] = 0, o[0]);

	while(!empty(pq)) {
		auto [dist, u] = pq.top(); pq.pop();
		if((dist *= -1) != d[u]) continue;
		for(auto [v, w] : g[u]) if(d[v] > dist + w)
			pq.emplace(-(d[v] = dist + w), v);
	}

	cout << d[o[1]];
}

Compilation message (stderr)

portals.cpp: In function 'int main()':
portals.cpp:91:16: warning: 'o[1]' may be used uninitialized in this function [-Wmaybe-uninitialized]
   91 |  cout << d[o[1]];
      |                ^

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