답안 #466173

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
466173	2021-08-18T09:29:49 Z	prvocislo	포탈들 (BOI14_portals)	C++17	100 / 100	309 ms	45516 KB

portals

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <iomanip>
using namespace std;

const int maxr = 1005, maxrc = maxr * maxr;
int r, c, start = -1, finish = -1;
inline int id(const int &x, const int &y) { return x * c + y; }
int g[maxrc][4], wall[maxrc], nxt[maxrc][4], dist[maxrc];
string s[maxr];	
priority_queue<pair<int, int>> pq;
inline void check(const int &u, const int &d)
{
	if (d < dist[u]) dist[u] = d, pq.push({ -d, u });
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	for (int i = 0; i < maxrc; i++) for (int j = 0; j < 4; j++) g[i][j] = nxt[i][j] = -1;
	for (int i = 0; i < maxrc; i++) wall[i] = -1, dist[i] = 1e9 + 5;
	cin >> r >> c;
	s[0] = s[r + 1] = string(c + 2, '#');
	for (int i = 1; i <= r; i++) cin >> s[i], s[i].insert(s[i].begin(), '#'), s[i].push_back('#');
	r += 2, c += 2;
	queue<int> q;
	for (int i = 0; i < r; i++) for (int j = 0; j < c; j++)
	{
		if (s[i][j] == 'S') start = id(i, j);
		if (s[i][j] == 'C') finish = id(i, j);
		if (s[i][j] == '#') wall[id(i, j)] = 0, q.push(id(i, j));
		if (i && s[i - 1][j] != '#')			g[id(i, j)][0] = id(i - 1, j);
		if (i < r - 1 && s[i + 1][j] != '#')	g[id(i, j)][1] = id(i + 1, j);
		if (j && s[i][j - 1] != '#')			g[id(i, j)][2] = id(i, j - 1);
		if (j < c - 1 && s[i][j + 1] != '#')	g[id(i, j)][3] = id(i, j + 1);
		if (i && s[i - 1][j] == '#')			nxt[id(i, j)][0] = id(i, j);
		if (i < r - 1 && s[i + 1][j] == '#')	nxt[id(i, j)][1] = id(i, j);
		if (j && s[i][j - 1] == '#')			nxt[id(i, j)][2] = id(i, j);
		if (j < c - 1 && s[i][j + 1] == '#')	nxt[id(i, j)][3] = id(i, j);
	}
	while (!q.empty())
	{
		int i = q.front();
		q.pop();
		for (int j = 0; j < 4; j++) if (g[i][j] != -1 && wall[g[i][j]] == -1)
			wall[g[i][j]] = wall[i] + 1, q.push(g[i][j]);
	}
	for (int i = 1; i < r; i++) for (int j = 0; j < c; j++)		if (nxt[id(i, j)][0] == -1) nxt[id(i, j)][0] = nxt[id(i - 1, j)][0];
	for (int i = r-2; i >= 0; i--) for (int j = 0; j < c; j++)	if (nxt[id(i, j)][1] == -1) nxt[id(i, j)][1] = nxt[id(i + 1, j)][1];
	for (int i = 0; i < r; i++) for (int j = 1; j < c; j++)		if (nxt[id(i, j)][2] == -1) nxt[id(i, j)][2] = nxt[id(i, j - 1)][2];
	for (int i = 0; i < r; i++) for (int j = c-2; j >= 0; j--)	if (nxt[id(i, j)][3] == -1) nxt[id(i, j)][3] = nxt[id(i, j + 1)][3];
	check(start, 0);
	while (!pq.empty())
	{
		int u = pq.top().second, d = -pq.top().first;
		pq.pop();
		if (dist[u] != d) continue;
		for (int i = 0; i < 4; i++) if (g[u][i] != -1) check(g[u][i], d + 1);
		for (int i = 0; i < 4; i++) check(nxt[u][i], d + wall[u]);
	}
	cout << dist[finish] << "\n";
	return 0;
}

Subtask #1
11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	20 ms	39856 KB	Output is correct
2	Correct	20 ms	39800 KB	Output is correct
3	Correct	20 ms	39864 KB	Output is correct
4	Correct	21 ms	39832 KB	Output is correct
5	Correct	22 ms	39860 KB	Output is correct
6	Correct	20 ms	39756 KB	Output is correct
7	Correct	20 ms	39756 KB	Output is correct
8	Correct	22 ms	39784 KB	Output is correct
9	Correct	21 ms	39776 KB	Output is correct
10	Correct	25 ms	39852 KB	Output is correct

Subtask #2
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	21 ms	39856 KB	Output is correct
2	Correct	20 ms	39756 KB	Output is correct
3	Correct	23 ms	39780 KB	Output is correct
4	Correct	22 ms	39800 KB	Output is correct
5	Correct	21 ms	39756 KB	Output is correct
6	Correct	22 ms	39804 KB	Output is correct
7	Correct	21 ms	39800 KB	Output is correct
8	Correct	21 ms	39756 KB	Output is correct
9	Correct	21 ms	39884 KB	Output is correct
10	Correct	21 ms	39756 KB	Output is correct
11	Correct	21 ms	39832 KB	Output is correct
12	Correct	21 ms	39884 KB	Output is correct
13	Correct	25 ms	39748 KB	Output is correct
14	Correct	21 ms	39756 KB	Output is correct
15	Correct	21 ms	39884 KB	Output is correct
16	Correct	20 ms	39872 KB	Output is correct

Subtask #3
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	20 ms	39852 KB	Output is correct
2	Correct	20 ms	39756 KB	Output is correct
3	Correct	21 ms	39880 KB	Output is correct
4	Correct	22 ms	39756 KB	Output is correct
5	Correct	27 ms	40140 KB	Output is correct
6	Correct	27 ms	39924 KB	Output is correct
7	Correct	27 ms	40016 KB	Output is correct
8	Correct	24 ms	39956 KB	Output is correct

Subtask #4
19.0 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Correct	21 ms	39800 KB	Output is correct
2	Correct	20 ms	39856 KB	Output is correct
3	Correct	21 ms	39840 KB	Output is correct
4	Correct	21 ms	39812 KB	Output is correct
5	Correct	21 ms	39852 KB	Output is correct
6	Correct	22 ms	39844 KB	Output is correct
7	Correct	21 ms	39844 KB	Output is correct
8	Correct	21 ms	39756 KB	Output is correct
9	Correct	21 ms	39884 KB	Output is correct
10	Correct	21 ms	39884 KB	Output is correct
11	Correct	21 ms	39892 KB	Output is correct
12	Correct	21 ms	39880 KB	Output is correct
13	Correct	21 ms	39884 KB	Output is correct
14	Correct	26 ms	39940 KB	Output is correct
15	Correct	31 ms	40016 KB	Output is correct
16	Correct	28 ms	40012 KB	Output is correct
17	Correct	27 ms	40012 KB	Output is correct
18	Correct	29 ms	40008 KB	Output is correct
19	Correct	27 ms	39884 KB	Output is correct
20	Correct	27 ms	39932 KB	Output is correct
21	Correct	27 ms	39972 KB	Output is correct
22	Correct	27 ms	40052 KB	Output is correct
23	Correct	27 ms	40008 KB	Output is correct
24	Correct	27 ms	39968 KB	Output is correct
25	Correct	21 ms	39840 KB	Output is correct
26	Correct	22 ms	39856 KB	Output is correct
27	Correct	20 ms	39756 KB	Output is correct
28	Correct	24 ms	40012 KB	Output is correct

Subtask #5
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	21 ms	39788 KB	Output is correct
2	Correct	21 ms	39756 KB	Output is correct
3	Correct	21 ms	39800 KB	Output is correct
4	Correct	21 ms	39828 KB	Output is correct
5	Correct	24 ms	39832 KB	Output is correct
6	Correct	21 ms	39796 KB	Output is correct
7	Correct	22 ms	39796 KB	Output is correct
8	Correct	22 ms	39756 KB	Output is correct
9	Correct	21 ms	39844 KB	Output is correct
10	Correct	21 ms	39872 KB	Output is correct
11	Correct	22 ms	39832 KB	Output is correct
12	Correct	23 ms	39776 KB	Output is correct
13	Correct	21 ms	39808 KB	Output is correct
14	Correct	26 ms	39952 KB	Output is correct
15	Correct	27 ms	40096 KB	Output is correct
16	Correct	27 ms	40084 KB	Output is correct
17	Correct	29 ms	39968 KB	Output is correct
18	Correct	27 ms	40044 KB	Output is correct
19	Correct	30 ms	39900 KB	Output is correct
20	Correct	28 ms	39884 KB	Output is correct
21	Correct	26 ms	39948 KB	Output is correct
22	Correct	26 ms	40004 KB	Output is correct
23	Correct	32 ms	40024 KB	Output is correct
24	Correct	185 ms	43812 KB	Output is correct
25	Correct	309 ms	42116 KB	Output is correct
26	Correct	274 ms	42136 KB	Output is correct
27	Correct	242 ms	42848 KB	Output is correct
28	Correct	173 ms	45164 KB	Output is correct
29	Correct	193 ms	45164 KB	Output is correct
30	Correct	211 ms	45256 KB	Output is correct
31	Correct	34 ms	40012 KB	Output is correct
32	Correct	267 ms	42860 KB	Output is correct
33	Correct	24 ms	39884 KB	Output is correct
34	Correct	21 ms	39756 KB	Output is correct
35	Correct	226 ms	43780 KB	Output is correct
36	Correct	23 ms	39816 KB	Output is correct
37	Correct	24 ms	40012 KB	Output is correct
38	Correct	85 ms	45516 KB	Output is correct
39	Correct	127 ms	44904 KB	Output is correct

답안 #466173

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