Submission #725284

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
725284	2023-04-17T07:07:36 Z	Radin_Zahedi2	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	761 ms	134780 KB

tracks

#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
using ll = long long;
using ld = long double;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define sz(x) (int)x.size()
//#define endl '\n'
const int mod = 1e9 + 7;
const int inf = 2e9 + 5;
const ll linf = 9e18 + 5;


int n, m;
const int N = 4e3 + 5;
char c[N][N];

int dist[N][N];

void init() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			c[i][j] = '.';
		}
	}
}

void input() {
	cin >> n >> m;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> c[i][j];
		}
	}
}

void bfs() {
	deque<pair<int, int>> dq;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			dist[i][j] = inf;
		}
	}


	dist[1][1] = 1;
	dq.push_back(mp(1, 1));

	while (!dq.empty()) {
		int x = dq.front().fi;
		int y = dq.front().se;
		dq.pop_front();

		for (int dx = -1; dx <= 1; dx++) {
			for (int dy = -1; dy <= 1; dy++) {
				if (abs(dx) + abs(dy) != 1) {
					continue;
				}

				if (dist[x + dx][y + dy] != inf) {
					continue;
				}

				if (c[x + dx][y + dy] == '.') {
					continue;
				}

				if (c[x + dx][y + dy] != c[x][y] && dist[x + dx][y + dy] > dist[x][y] + 1) {
					dist[x + dx][y + dy] = dist[x][y] + 1;
					dq.push_back(mp(x + dx, y + dy));
				}
				else if (dist[x + dx][y + dy] > dist[x][y]) {
					dist[x + dx][y + dy] = dist[x][y];
					dq.push_front(mp(x + dx, y + dy));
				}
			}
		}
	}
}

void solve() {
	bfs();

	int ans = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (dist[i][j] != inf) {
				ans = max(ans, dist[i][j]);
			}
		}
	}

	cout << ans;
}

void output() {
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int number_of_testcases = 1;
	//cin >> number_of_testcases;
	while (number_of_testcases--) {
		init();

		input();

		solve();

		output();
	}

	return 0;
}

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	5460 KB	Output is correct
2	Correct	1 ms	468 KB	Output is correct
3	Correct	1 ms	704 KB	Output is correct
4	Correct	8 ms	5144 KB	Output is correct
5	Correct	5 ms	3028 KB	Output is correct
6	Correct	1 ms	456 KB	Output is correct
7	Correct	1 ms	724 KB	Output is correct
8	Correct	1 ms	724 KB	Output is correct
9	Correct	1 ms	1108 KB	Output is correct
10	Correct	3 ms	2516 KB	Output is correct
11	Correct	3 ms	2132 KB	Output is correct
12	Correct	6 ms	3028 KB	Output is correct
13	Correct	4 ms	3028 KB	Output is correct
14	Correct	4 ms	3024 KB	Output is correct
15	Correct	12 ms	5460 KB	Output is correct
16	Correct	14 ms	5460 KB	Output is correct
17	Correct	11 ms	5204 KB	Output is correct
18	Correct	9 ms	5204 KB	Output is correct

Subtask #2

70.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	14 ms	30876 KB	Output is correct
2	Correct	55 ms	17896 KB	Output is correct
3	Correct	358 ms	94280 KB	Output is correct
4	Correct	122 ms	33632 KB	Output is correct
5	Correct	236 ms	67808 KB	Output is correct
6	Correct	760 ms	109456 KB	Output is correct
7	Correct	16 ms	32212 KB	Output is correct
8	Correct	13 ms	30840 KB	Output is correct
9	Correct	3 ms	720 KB	Output is correct
10	Correct	2 ms	468 KB	Output is correct
11	Correct	14 ms	31700 KB	Output is correct
12	Correct	2 ms	1620 KB	Output is correct
13	Correct	59 ms	17796 KB	Output is correct
14	Correct	34 ms	11988 KB	Output is correct
15	Correct	29 ms	13120 KB	Output is correct
16	Correct	25 ms	6608 KB	Output is correct
17	Correct	138 ms	36148 KB	Output is correct
18	Correct	122 ms	35744 KB	Output is correct
19	Correct	124 ms	33580 KB	Output is correct
20	Correct	82 ms	31060 KB	Output is correct
21	Correct	217 ms	70176 KB	Output is correct
22	Correct	261 ms	67824 KB	Output is correct
23	Correct	260 ms	56916 KB	Output is correct
24	Correct	209 ms	69476 KB	Output is correct
25	Correct	538 ms	94236 KB	Output is correct
26	Correct	423 ms	131044 KB	Output is correct
27	Correct	592 ms	134780 KB	Output is correct
28	Correct	717 ms	109376 KB	Output is correct
29	Correct	761 ms	106620 KB	Output is correct
30	Correct	682 ms	109760 KB	Output is correct
31	Correct	553 ms	73480 KB	Output is correct
32	Correct	593 ms	117256 KB	Output is correct