oj.uz

Submission #465187

# Submission time Handle Problem Language Result Execution time Memory
465187 2021-08-15T10:18:34 Z Elias Awesome Arrowland Adventure (eJOI19_adventure) C++17
34 / 100
 1 ms 332 KB 
#include <bits/stdc++.h>

using namespace std;

#define int long long

vector<vector<pair<int, int>>> adj;
vector<bool> visited;

int dijkstra(int s, int e)
{
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	pq.push({0, s});
	visited[0] = true;

	while (pq.size())
	{
		auto [dist, x] = pq.top();
		pq.pop();
		if (x == e)
			return dist;
		for (auto [d, c] : adj[x])
		{
			if (visited[c])
				continue;
			pq.push({d + dist, c});
			visited[c] = true;
		}
	}

	return -1;
}

signed main()
{
	cin.tie(0);
	ios_base::sync_with_stdio(false);

	int n, m;
	cin >> m >> n;

	adj = vector<vector<pair<int, int>>>(n * m);
	visited = vector<bool>(n * m, false);

	vector<pair<int, int>> dirs{{0, -1}, {1, 0}, {0, 1}, {-1, 0}};

	string row;

	for (int y = 0; y < m; y++)
	{
		cin >> row;
		for (int x = 0; x < n; x++)
		{
			int dir = row[x];
			if (dir == 'X')
				continue;
			if (dir == 'N')
				dir = 0;
			if (dir == 'E')
				dir = 3;
			if (dir == 'S')
				dir = 2;
			if (dir == 'W')
				dir = 1;

			for (auto [pX, pY] : dirs)
			{
				int dist = dir;
				dir = (dir + 1) % 4;

				int newX = x + pX;
				int newY = y + pY;
				if (newX < 0 || newX >= n || newY < 0 || newY >= m)
					continue;

				adj[x + y * n].push_back({dist, newX + newY * n});
			}
		}
	}

	//throw exception();

	cout << dijkstra(0, n * m - 1);
}

Subtask #1
10.0 / 10.0

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

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 0 ms 204 KB Output is correct
19 Correct 0 ms 204 KB Output is correct
20 Correct 1 ms 332 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Incorrect 0 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 0 ms 204 KB Output is correct
19 Correct 0 ms 204 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 0 ms 204 KB Output is correct
22 Correct 0 ms 204 KB Output is correct
23 Correct 0 ms 204 KB Output is correct
24 Correct 0 ms 204 KB Output is correct
25 Correct 1 ms 332 KB Output is correct
26 Incorrect 0 ms 204 KB Output isn't correct
27 Halted 0 ms 0 KB -