oj.uz

Submission #466165

# Submission time Handle Problem Language Result Execution time Memory
466165 2021-08-18T08:59:27 Z prvocislo Portals (BOI14_portals) C++17
70 / 100
 1000 ms 149120 KB 
#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];
vector<pair<int, int> > g2[maxrc];
string s[maxr];
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++) dist[i] = wall[i] = -1;
	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];
	for (int i = 0; i < r; i++) for (int j = 0; j < c; j++) if (s[i][j] != '#')
	{
		for (int k = 0; k < 4; k++)
		{
			if (g[id(i, j)][k] != -1) g2[id(i, j)].push_back({ g[id(i, j)][k], 1 });
			g2[id(i, j)].push_back({ nxt[id(i, j)][k], wall[id(i, j)] });
		}
	}
	priority_queue<pair<int, int>> pq;
	pq.push({ 0, start });
	while (!pq.empty())
	{
		int u = pq.top().second, d = -pq.top().first;
		pq.pop();
		if (dist[u] != -1) continue;
		dist[u] = d;
		for (pair<int, int> v : g2[u]) if (dist[v.first] == -1)
			pq.push({ -d - v.second, v.first });
	}
	/*for (int i = 0; i < r; i++)
	{
		for (int j = 0; j < c; j++) cout << setw(3) << dist[id(i, j)] << " ";
		cout << "\n";
	}*/
	cout << dist[finish] << "\n";
	return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 63516 KB Output is correct
2 Correct 34 ms 63480 KB Output is correct
3 Correct 35 ms 63484 KB Output is correct
4 Correct 34 ms 63464 KB Output is correct
5 Correct 35 ms 63548 KB Output is correct
6 Correct 36 ms 63528 KB Output is correct
7 Correct 34 ms 63492 KB Output is correct
8 Correct 35 ms 63556 KB Output is correct
9 Correct 35 ms 63564 KB Output is correct
10 Correct 35 ms 63528 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 63580 KB Output is correct
2 Correct 34 ms 63536 KB Output is correct
3 Correct 35 ms 63532 KB Output is correct
4 Correct 35 ms 63528 KB Output is correct
5 Correct 35 ms 63476 KB Output is correct
6 Correct 37 ms 63552 KB Output is correct
7 Correct 34 ms 63596 KB Output is correct
8 Correct 35 ms 63532 KB Output is correct
9 Correct 36 ms 63688 KB Output is correct
10 Correct 36 ms 63780 KB Output is correct
11 Correct 36 ms 63704 KB Output is correct
12 Correct 36 ms 63672 KB Output is correct
13 Correct 36 ms 63716 KB Output is correct
14 Correct 38 ms 63564 KB Output is correct
15 Correct 36 ms 63684 KB Output is correct
16 Correct 35 ms 63540 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 63468 KB Output is correct
2 Correct 34 ms 63564 KB Output is correct
3 Correct 34 ms 63560 KB Output is correct
4 Correct 37 ms 63504 KB Output is correct
5 Correct 47 ms 65364 KB Output is correct
6 Correct 49 ms 65568 KB Output is correct
7 Correct 57 ms 65688 KB Output is correct
8 Correct 43 ms 65708 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 63472 KB Output is correct
2 Correct 36 ms 63504 KB Output is correct
3 Correct 36 ms 63536 KB Output is correct
4 Correct 35 ms 63452 KB Output is correct
5 Correct 35 ms 63564 KB Output is correct
6 Correct 37 ms 63472 KB Output is correct
7 Correct 36 ms 63508 KB Output is correct
8 Correct 35 ms 63492 KB Output is correct
9 Correct 36 ms 63684 KB Output is correct
10 Correct 38 ms 63904 KB Output is correct
11 Correct 37 ms 63796 KB Output is correct
12 Correct 37 ms 63700 KB Output is correct
13 Correct 41 ms 63684 KB Output is correct
14 Correct 53 ms 65476 KB Output is correct
15 Correct 50 ms 65588 KB Output is correct
16 Correct 51 ms 65676 KB Output is correct
17 Correct 51 ms 65720 KB Output is correct
18 Correct 56 ms 66116 KB Output is correct
19 Correct 62 ms 66836 KB Output is correct
20 Correct 73 ms 67924 KB Output is correct
21 Correct 48 ms 65556 KB Output is correct
22 Correct 54 ms 65476 KB Output is correct
23 Correct 50 ms 65604 KB Output is correct
24 Correct 53 ms 66824 KB Output is correct
25 Correct 35 ms 63476 KB Output is correct
26 Correct 35 ms 63632 KB Output is correct
27 Correct 34 ms 63572 KB Output is correct
28 Correct 42 ms 65804 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 63460 KB Output is correct
2 Correct 37 ms 63556 KB Output is correct
3 Correct 35 ms 63564 KB Output is correct
4 Correct 34 ms 63560 KB Output is correct
5 Correct 35 ms 63496 KB Output is correct
6 Correct 36 ms 63580 KB Output is correct
7 Correct 35 ms 63524 KB Output is correct
8 Correct 35 ms 63476 KB Output is correct
9 Correct 35 ms 63716 KB Output is correct
10 Correct 37 ms 63884 KB Output is correct
11 Correct 35 ms 63684 KB Output is correct
12 Correct 35 ms 63628 KB Output is correct
13 Correct 37 ms 63716 KB Output is correct
14 Correct 48 ms 65468 KB Output is correct
15 Correct 48 ms 65476 KB Output is correct
16 Correct 51 ms 65812 KB Output is correct
17 Correct 50 ms 65632 KB Output is correct
18 Correct 56 ms 66160 KB Output is correct
19 Correct 62 ms 66884 KB Output is correct
20 Correct 74 ms 67968 KB Output is correct
21 Correct 46 ms 65456 KB Output is correct
22 Correct 49 ms 65472 KB Output is correct
23 Correct 50 ms 65612 KB Output is correct
24 Correct 553 ms 120380 KB Output is correct
25 Correct 870 ms 145164 KB Output is correct
26 Execution timed out 1056 ms 149120 KB Time limit exceeded
27 Halted 0 ms 0 KB -