oj.uz

답안 #876378

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
876378 2023-11-21T16:06:16 Z vjudge1 Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 1198 ms 167200 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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