Submission #904016

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
904016	2024-01-11T17:17:44 Z	Irate	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	770 ms	122888 KB

tracks

#include<bits/stdc++.h>
using namespace std;
int n, m;
bool check(int i, int j){
  return (i >= 0 && i < n && j >= 0 && j < m);
}
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	vector<vector<char>>grid(n, vector<char>(m));
	for(int i = 0;i < n;++i){
		for(int j = 0;j < m;++j){
			cin >> grid[i][j];
		}
	}
	vector<vector<int>>dist(n, vector<int>(m, 1e9));
	dist[0][0] = 0;
	deque<pair<int, int>>q;
	q.push_front({0, 0});
	while(!q.empty()){
		int x = q.front().first, y = q.front().second;
		q.pop_front();
        for(int i = 0;i < 4;++i){
        	int cur_x = x + dx[i], cur_y = y + dy[i];
        	if(check(cur_x, cur_y) && dist[cur_x][cur_y] > dist[x][y] + (grid[x][y] != grid[cur_x][cur_y]) && grid[cur_x][cur_y] != '.'){
        		if(grid[x][y] != grid[cur_x][cur_y])q.push_back({cur_x, cur_y});
        		else q.push_front({cur_x, cur_y});
        		dist[cur_x][cur_y] = dist[x][y] + (grid[x][y] != grid[cur_x][cur_y]);
        	}
        }
	}
	int mx = 0;
	for(int i = 0;i < n;++i){
		for(int j = 0;j < m;++j){
			if(dist[i][j] != 1e9)mx = max(mx, dist[i][j]);
		}
	}
	cout << mx + 1;
}

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	1972 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	6 ms	1368 KB	Output is correct
5	Correct	3 ms	860 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	2 ms	732 KB	Output is correct
11	Correct	2 ms	604 KB	Output is correct
12	Correct	4 ms	1024 KB	Output is correct
13	Correct	2 ms	860 KB	Output is correct
14	Correct	3 ms	1112 KB	Output is correct
15	Correct	9 ms	1888 KB	Output is correct
16	Correct	10 ms	1976 KB	Output is correct
17	Correct	12 ms	2040 KB	Output is correct
18	Correct	6 ms	1384 KB	Output is correct

Subtask #2

70.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	872 KB	Output is correct
2	Correct	60 ms	9720 KB	Output is correct
3	Correct	320 ms	94692 KB	Output is correct
4	Correct	95 ms	22492 KB	Output is correct
5	Correct	178 ms	53352 KB	Output is correct
6	Correct	706 ms	108968 KB	Output is correct
7	Correct	2 ms	860 KB	Output is correct
8	Correct	2 ms	860 KB	Output is correct
9	Correct	2 ms	604 KB	Output is correct
10	Correct	1 ms	604 KB	Output is correct
11	Correct	1 ms	860 KB	Output is correct
12	Correct	1 ms	600 KB	Output is correct
13	Correct	53 ms	9712 KB	Output is correct
14	Correct	25 ms	5720 KB	Output is correct
15	Correct	22 ms	6236 KB	Output is correct
16	Correct	20 ms	4188 KB	Output is correct
17	Correct	111 ms	24420 KB	Output is correct
18	Correct	86 ms	24012 KB	Output is correct
19	Correct	79 ms	22592 KB	Output is correct
20	Correct	81 ms	20732 KB	Output is correct
21	Correct	199 ms	55376 KB	Output is correct
22	Correct	186 ms	53352 KB	Output is correct
23	Correct	227 ms	45904 KB	Output is correct
24	Correct	176 ms	53948 KB	Output is correct
25	Correct	496 ms	94680 KB	Output is correct
26	Correct	750 ms	122888 KB	Output is correct
27	Correct	688 ms	120504 KB	Output is correct
28	Correct	720 ms	109384 KB	Output is correct
29	Correct	770 ms	106332 KB	Output is correct
30	Correct	729 ms	111352 KB	Output is correct
31	Correct	473 ms	61176 KB	Output is correct
32	Correct	737 ms	118612 KB	Output is correct