Submission #440785

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
440785	2021-07-03T03:08:43 Z	HadiHosseini	Tracks in the Snow (BOI13_tracks)	C++14	9.89583 / 100	1304 ms	144768 KB

tracks

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

const int N = 4001; 
const int M = 4001;
int n, m;
char a[N][M]; 
int d[N][M];
int ans = 1;
bool visited[N][M];

int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

bool inside(int r, int c) {
	return !(r < 0 || r > n || c < 0 || c > m || a[r][c] == '.'); 
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
 
 cin >> n >> m;
 for(int i = 0 ; i < n; i++){
 	string s; cin >> s;
 	for(int j = 0 ; j < m; j++){
 		 a[i][j] = s[j];
 	}
 }

 deque<pair<int, int>> q;
 visited[0][0] = true;
 q.push_back({0, 0});
 while(!q.empty()){
 	auto node = q.front();
 	q.pop_front();
 	ans = max(ans, d[node.first][node.second]);
 	for(int i = 0 ; i < 4; i++){
 	 int x = node.first + dx[i]; int y = node.second + dy[i];
 	 if(inside(x, y) && d[x][y] == 0 && !visited[x][y]){
 	   if(a[node.first][node.second] == a[x][y]){
 	   	d[x][y] = d[node.first][node.second];
 	   	q.push_front({x, y});
 	   	visited[x][y] = true;
 	   }
 	   else {
 	   	d[x][y] = d[node.first][node.second] + 1;
 	   	q.push_back({x, y});
 	   	visited[x][y] = true;
 	   }
 	 }
 	}
 }

 cout << ans << "\n";



	return 0;
}                

Subtask #1

3.33333333333 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	25 ms	7376 KB	Output isn't correct
2	Incorrect	1 ms	448 KB	Output isn't correct
3	Incorrect	1 ms	844 KB	Output isn't correct
4	Incorrect	14 ms	7116 KB	Output isn't correct
5	Incorrect	6 ms	4044 KB	Output isn't correct
6	Incorrect	1 ms	460 KB	Output isn't correct
7	Incorrect	1 ms	844 KB	Output isn't correct
8	Correct	2 ms	972 KB	Output is correct
9	Incorrect	2 ms	1480 KB	Output isn't correct
10	Incorrect	4 ms	3460 KB	Output isn't correct
11	Correct	5 ms	2892 KB	Output is correct
12	Incorrect	8 ms	4228 KB	Output isn't correct
13	Incorrect	6 ms	4068 KB	Output isn't correct
14	Incorrect	6 ms	4044 KB	Output isn't correct
15	Incorrect	16 ms	7372 KB	Output isn't correct
16	Incorrect	23 ms	7320 KB	Output isn't correct
17	Incorrect	14 ms	7104 KB	Output isn't correct
18	Incorrect	17 ms	7096 KB	Output isn't correct

Subtask #2

6.5625 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	30 ms	45772 KB	Output isn't correct
2	Incorrect	58 ms	21464 KB	Output isn't correct
3	Incorrect	263 ms	89080 KB	Output isn't correct
4	Incorrect	119 ms	40408 KB	Output isn't correct
5	Incorrect	469 ms	68096 KB	Output isn't correct
6	Incorrect	955 ms	123532 KB	Output isn't correct
7	Incorrect	37 ms	47936 KB	Output isn't correct
8	Incorrect	34 ms	45764 KB	Output isn't correct
9	Incorrect	2 ms	716 KB	Output isn't correct
10	Incorrect	1 ms	456 KB	Output isn't correct
11	Incorrect	36 ms	46960 KB	Output isn't correct
12	Incorrect	3 ms	2124 KB	Output isn't correct
13	Incorrect	63 ms	21416 KB	Output isn't correct
14	Incorrect	38 ms	14732 KB	Output isn't correct
15	Incorrect	33 ms	17072 KB	Output isn't correct
16	Incorrect	27 ms	7776 KB	Output isn't correct
17	Incorrect	149 ms	40104 KB	Output isn't correct
18	Incorrect	114 ms	43624 KB	Output isn't correct
19	Incorrect	137 ms	40332 KB	Output isn't correct
20	Incorrect	68 ms	32384 KB	Output isn't correct
21	Incorrect	159 ms	73948 KB	Output isn't correct
22	Incorrect	513 ms	68092 KB	Output isn't correct
23	Incorrect	265 ms	58876 KB	Output isn't correct
24	Incorrect	167 ms	62148 KB	Output isn't correct
25	Incorrect	1304 ms	110000 KB	Output isn't correct
26	Correct	543 ms	144768 KB	Output is correct
27	Incorrect	680 ms	136640 KB	Output isn't correct
28	Incorrect	980 ms	123440 KB	Output isn't correct
29	Correct	908 ms	121972 KB	Output is correct
30	Correct	786 ms	125648 KB	Output is correct
31	Incorrect	873 ms	86260 KB	Output isn't correct
32	Incorrect	531 ms	124516 KB	Output isn't correct