Submission #876378

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
876378	2023-11-21T16:06:16 Z	vjudge1	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	1198 ms	167200 KB

tracks

#include <bits/stdc++.h>
using namespace std;

const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};
const int MAXN = 4000 + 5;
int g[MAXN][MAXN];
int n, m;

int hsh(int i, int j)
{
	return (i * m) + j;
}

int main()
{
	cin >> n >> m;
	bool visited[n][m];
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			char ch;
			cin >> ch;
			if (ch == '.')
				g[i][j] = 0;
			if (ch == 'R')
				g[i][j] = 1;
			if (ch == 'F')
				g[i][j] = 2;
			visited[i][j] = false;
		}
	}
	vector<int> dx = {0, 1, 0, -1};
	vector<int> dy = {1, 0, -1, 0};
	int mxn = hsh(n - 1, m - 1);
	vector<int> dd(mxn + 1, 1e9);
	deque<pair<int, int>> q;
	q.push_front({0, 0});
	dd[0] = 1;
	int ans = 0;
	while (!q.empty())
	{
		pair<int, int> v = q.front();
		int vhsh = hsh(v.first, v.second);
		q.pop_front();
		ans = max(ans, dd[vhsh]);
		if (visited[v.first][v.second])
			continue;
		visited[v.first][v.second] = true;
		int r = v.first;
		int c = v.second;
		for (int k = 0; k < 4; k++)
		{
			int rr = r + dx[k];
			int cc = c + dy[k];
			if (rr < 0 || rr >= n || cc < 0 || cc >= m)
				continue;
			if (visited[rr][cc])
				continue;
			if (g[rr][cc] == 0)
				continue;
			int khsh = hsh(rr, cc);
			if (dd[vhsh] + (g[r][c] != g[rr][cc]) < dd[khsh])
			{
				dd[khsh] = dd[vhsh] + (g[r][c] != g[rr][cc]);
				if (g[rr][cc] != g[r][c])
					q.push_back({rr, cc});
				else
					q.push_front({rr, cc});
			}
		}
	}
	return cout << ans, 0;
	//Olampiad ye tale bood
}

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	21 ms	9820 KB	Output is correct
2	Correct	1 ms	2396 KB	Output is correct
3	Correct	1 ms	2396 KB	Output is correct
4	Correct	11 ms	9564 KB	Output is correct
5	Correct	5 ms	7004 KB	Output is correct
6	Correct	1 ms	2396 KB	Output is correct
7	Correct	1 ms	2396 KB	Output is correct
8	Correct	1 ms	2396 KB	Output is correct
9	Correct	1 ms	2648 KB	Output is correct
10	Correct	4 ms	4700 KB	Output is correct
11	Correct	3 ms	4700 KB	Output is correct
12	Correct	8 ms	7004 KB	Output is correct
13	Correct	5 ms	7004 KB	Output is correct
14	Correct	5 ms	7004 KB	Output is correct
15	Correct	18 ms	9820 KB	Output is correct
16	Correct	20 ms	9820 KB	Output is correct
17	Correct	17 ms	9896 KB	Output is correct
18	Correct	11 ms	9564 KB	Output is correct

Subtask #2

70.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	62300 KB	Output is correct
2	Correct	86 ms	28688 KB	Output is correct
3	Correct	683 ms	141440 KB	Output is correct
4	Correct	171 ms	49492 KB	Output is correct
5	Correct	367 ms	91596 KB	Output is correct
6	Correct	1198 ms	155868 KB	Output is correct
7	Correct	9 ms	62296 KB	Output is correct
8	Correct	9 ms	62104 KB	Output is correct
9	Correct	4 ms	2908 KB	Output is correct
10	Correct	2 ms	604 KB	Output is correct
11	Correct	9 ms	62236 KB	Output is correct
12	Correct	2 ms	4700 KB	Output is correct
13	Correct	85 ms	28700 KB	Output is correct
14	Correct	49 ms	19284 KB	Output is correct
15	Correct	52 ms	21588 KB	Output is correct
16	Correct	39 ms	9812 KB	Output is correct
17	Correct	215 ms	53076 KB	Output is correct
18	Correct	207 ms	53072 KB	Output is correct
19	Correct	170 ms	49544 KB	Output is correct
20	Correct	152 ms	45928 KB	Output is correct
21	Correct	405 ms	95572 KB	Output is correct
22	Correct	367 ms	91672 KB	Output is correct
23	Correct	416 ms	79448 KB	Output is correct
24	Correct	390 ms	94332 KB	Output is correct
25	Correct	926 ms	141648 KB	Output is correct
26	Correct	999 ms	166248 KB	Output is correct
27	Correct	1084 ms	167200 KB	Output is correct
28	Correct	1172 ms	155672 KB	Output is correct
29	Correct	1154 ms	153168 KB	Output is correct
30	Correct	1113 ms	157468 KB	Output is correct
31	Correct	819 ms	102228 KB	Output is correct
32	Correct	1064 ms	165472 KB	Output is correct