Submission #465186

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
465186	2021-08-15T10:16:29 Z	Elias	Awesome Arrowland Adventure (eJOI19_adventure)	C++17	34 / 100	2000 ms	66120 KB

adventure

#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});
	while (pq.size())
	{
		auto [dist, x] = pq.top();
		pq.pop();
		visited[x] = true;
		if (x == e)
			return dist;
		for (auto [d, c] : adj[x])
		{
			if (visited[c])
				continue;
			pq.push({d + dist, c});
		}
	}

	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	332 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	1 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	0 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	332 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	1 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	0 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	0 ms	204 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	0 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	1 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	1 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	Correct	0 ms	204 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Execution timed out	2070 ms	66120 KB	Time limit exceeded
6	Halted	0 ms	0 KB	-

Subtask #5

0 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	332 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	1 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	0 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	0 ms	204 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	0 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	1 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	1 ms	204 KB	Output is correct
25	Correct	1 ms	332 KB	Output is correct
26	Correct	0 ms	204 KB	Output is correct
27	Correct	1 ms	332 KB	Output is correct
28	Correct	1 ms	332 KB	Output is correct
29	Execution timed out	2070 ms	66120 KB	Time limit exceeded
30	Halted	0 ms	0 KB	-