Submission #555346

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
555346	2022-04-30T14:29:18 Z	sidon	Portals (BOI14_portals)	C++17	100 / 100	669 ms	108424 KB

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

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.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	224 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	320 KB	Output is correct
9	Correct	0 ms	324 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct

Subtask #2
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	324 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	596 KB	Output is correct
10	Correct	1 ms	596 KB	Output is correct
11	Correct	1 ms	468 KB	Output is correct
12	Correct	1 ms	468 KB	Output is correct
13	Correct	1 ms	448 KB	Output is correct
14	Correct	0 ms	316 KB	Output is correct
15	Correct	1 ms	468 KB	Output is correct
16	Correct	1 ms	320 KB	Output is correct

Subtask #3
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	9 ms	2772 KB	Output is correct
6	Correct	11 ms	2948 KB	Output is correct
7	Correct	13 ms	3460 KB	Output is correct
8	Correct	7 ms	2880 KB	Output is correct

Subtask #4
19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	316 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	328 KB	Output is correct
8	Correct	0 ms	324 KB	Output is correct
9	Correct	1 ms	596 KB	Output is correct
10	Correct	1 ms	596 KB	Output is correct
11	Correct	1 ms	468 KB	Output is correct
12	Correct	1 ms	468 KB	Output is correct
13	Correct	2 ms	468 KB	Output is correct
14	Correct	9 ms	2804 KB	Output is correct
15	Correct	10 ms	2920 KB	Output is correct
16	Correct	12 ms	3284 KB	Output is correct
17	Correct	12 ms	3412 KB	Output is correct
18	Correct	15 ms	4024 KB	Output is correct
19	Correct	19 ms	4580 KB	Output is correct
20	Correct	15 ms	4692 KB	Output is correct
21	Correct	9 ms	2836 KB	Output is correct
22	Correct	9 ms	2812 KB	Output is correct
23	Correct	10 ms	3028 KB	Output is correct
24	Correct	15 ms	4564 KB	Output is correct
25	Correct	1 ms	212 KB	Output is correct
26	Correct	1 ms	456 KB	Output is correct
27	Correct	1 ms	212 KB	Output is correct
28	Correct	7 ms	2796 KB	Output is correct

Subtask #5
30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	328 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	0 ms	320 KB	Output is correct
9	Correct	1 ms	580 KB	Output is correct
10	Correct	2 ms	596 KB	Output is correct
11	Correct	1 ms	468 KB	Output is correct
12	Correct	1 ms	468 KB	Output is correct
13	Correct	1 ms	468 KB	Output is correct
14	Correct	9 ms	2804 KB	Output is correct
15	Correct	10 ms	2900 KB	Output is correct
16	Correct	11 ms	3288 KB	Output is correct
17	Correct	11 ms	3412 KB	Output is correct
18	Correct	16 ms	4068 KB	Output is correct
19	Correct	17 ms	4580 KB	Output is correct
20	Correct	16 ms	4692 KB	Output is correct
21	Correct	10 ms	2900 KB	Output is correct
22	Correct	10 ms	2772 KB	Output is correct
23	Correct	10 ms	3088 KB	Output is correct
24	Correct	446 ms	83820 KB	Output is correct
25	Correct	669 ms	108424 KB	Output is correct
26	Correct	602 ms	108412 KB	Output is correct
27	Correct	600 ms	108144 KB	Output is correct
28	Correct	319 ms	61700 KB	Output is correct
29	Correct	341 ms	62556 KB	Output is correct
30	Correct	383 ms	64756 KB	Output is correct
31	Correct	15 ms	4564 KB	Output is correct
32	Correct	579 ms	108100 KB	Output is correct
33	Correct	0 ms	212 KB	Output is correct
34	Correct	1 ms	468 KB	Output is correct
35	Correct	405 ms	80820 KB	Output is correct
36	Correct	1 ms	212 KB	Output is correct
37	Correct	7 ms	2808 KB	Output is correct
38	Correct	273 ms	61464 KB	Output is correct
39	Correct	214 ms	53452 KB	Output is correct

Submission #555346

Compilation message

Subtask #1 11.0 / 11.0

Subtask #2 20.0 / 20.0

Subtask #3 20.0 / 20.0

Subtask #4 19.0 / 19.0

Subtask #5 30.0 / 30.0

Subtask #1
11.0 / 11.0

Subtask #2
20.0 / 20.0

Subtask #3
20.0 / 20.0

Subtask #4
19.0 / 19.0

Subtask #5
30.0 / 30.0