Submission #401797

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
401797	2021-05-10T20:41:46 Z	jli12345	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	1498 ms	144792 KB

tracks

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

typedef pair<int, int> pii;
#define f first
#define s second


int N, M;
char arr[4100][4100];

int depth[4100][4100];

struct comp{
	bool operator()(const pair<pii, int> &a, const pair<pii, int> &b){
		return a.s > b.s;
	}
};

int xd[4] = {1, -1, 0, 0};
int yd[4] = {0, 0, 1, -1};

int main(){
	cin >> N >> M;
	for (int i = 1; i <= N; i++){
		for (int j = 1; j <= M; j++){
			cin >> arr[i][j];
		}
	}
	deque<pair<pii, int>> dq;
	dq.push_back({{1, 1}, 1});
	depth[1][1] = 1;
	while (!dq.empty()){
		int x = dq.front().f.f;
		int y = dq.front().f.s;
		int w = dq.front().s;
		dq.pop_front();
		for (int i = 0; i < 4; i++){
			int nx = x+xd[i];
			int ny = y+yd[i];
			if (nx >= 1 && nx <= N && ny >= 1 && ny <= M && arr[nx][ny] != '.' && !depth[nx][ny]){
				if (arr[x][y] == arr[nx][ny]){
					depth[nx][ny] = depth[x][y];
					dq.push_front({{nx, ny}, depth[nx][ny]});
				} else {
					depth[nx][ny] = depth[x][y]+1;
					dq.push_back({{nx, ny}, depth[nx][ny]});
				}
			}
		}
	}
	int ans = 0;
	for (int i = 1; i <= N; i++){
		for (int j = 1; j <= M; j++){
			ans = max(ans, depth[i][j]);
		}
	}
	cout << ans << "\n";
}

Compilation message

tracks.cpp: In function 'int main()':
tracks.cpp:36:7: warning: unused variable 'w' [-Wunused-variable]
   36 |   int w = dq.front().s;
      |       ^

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	27 ms	5316 KB	Output is correct
2	Correct	1 ms	460 KB	Output is correct
3	Correct	1 ms	716 KB	Output is correct
4	Correct	18 ms	5220 KB	Output is correct
5	Correct	8 ms	2892 KB	Output is correct
6	Correct	1 ms	460 KB	Output is correct
7	Correct	1 ms	716 KB	Output is correct
8	Correct	1 ms	816 KB	Output is correct
9	Correct	2 ms	1100 KB	Output is correct
10	Correct	7 ms	2420 KB	Output is correct
11	Correct	5 ms	2124 KB	Output is correct
12	Correct	11 ms	3056 KB	Output is correct
13	Correct	8 ms	2892 KB	Output is correct
14	Correct	9 ms	2892 KB	Output is correct
15	Correct	26 ms	5172 KB	Output is correct
16	Correct	28 ms	5336 KB	Output is correct
17	Correct	23 ms	5148 KB	Output is correct
18	Correct	17 ms	5216 KB	Output is correct

Subtask #2

70.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 ms	31180 KB	Output is correct
2	Correct	131 ms	13788 KB	Output is correct
3	Correct	1103 ms	58808 KB	Output is correct
4	Correct	282 ms	29508 KB	Output is correct
5	Correct	683 ms	45120 KB	Output is correct
6	Correct	1493 ms	100660 KB	Output is correct
7	Correct	20 ms	32460 KB	Output is correct
8	Correct	20 ms	31184 KB	Output is correct
9	Correct	6 ms	564 KB	Output is correct
10	Correct	3 ms	332 KB	Output is correct
11	Correct	19 ms	31920 KB	Output is correct
12	Correct	3 ms	1612 KB	Output is correct
13	Correct	131 ms	13764 KB	Output is correct
14	Correct	76 ms	9668 KB	Output is correct
15	Correct	79 ms	12260 KB	Output is correct
16	Correct	56 ms	5200 KB	Output is correct
17	Correct	339 ms	25292 KB	Output is correct
18	Correct	309 ms	32080 KB	Output is correct
19	Correct	282 ms	29828 KB	Output is correct
20	Correct	248 ms	22468 KB	Output is correct
21	Correct	664 ms	43844 KB	Output is correct
22	Correct	674 ms	45112 KB	Output is correct
23	Correct	639 ms	36396 KB	Output is correct
24	Correct	643 ms	41312 KB	Output is correct
25	Correct	1328 ms	80688 KB	Output is correct
26	Correct	1067 ms	144792 KB	Output is correct
27	Correct	1385 ms	119996 KB	Output is correct
28	Correct	1498 ms	100740 KB	Output is correct
29	Correct	1488 ms	98528 KB	Output is correct
30	Correct	1429 ms	105296 KB	Output is correct
31	Correct	1059 ms	65116 KB	Output is correct
32	Correct	1317 ms	101548 KB	Output is correct