oj.uz

Submission #940536

# Submission time Handle Problem Language Result Execution time Memory
940536 2024-03-07T10:20:41 Z Reverberate Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 603 ms 241708 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define MAXN 4002

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

int n, m, depth[MAXN][MAXN], ans = 1;
char snow[MAXN][MAXN];

bool inside(int x, int y) {
	return (x > -1 && x < n && y > -1 && y < m && snow[x][y] != '.');
}

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>m;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			cin>>snow[i][j];
		}
	}
	memset(depth,0,sizeof(depth));
	deque<pair<int,int>>dq;
	dq.push_back({0,0});
	depth[0][0]=1;
	while(!dq.empty()){
		auto curr = dq.front();
		int r = curr.first, c = curr.second;
		dq.pop_front();
		ans = max(ans,depth[r][c]);
		for(int i=0;i<4;i++){
			int nr = r+dx[i], nc = c+dy[i];
			if(inside(nr,nc)&&depth[nr][nc]==0){
				if(snow[r][c]==snow[nr][nc]){
					depth[nr][nc] = depth[r][c];
					dq.push_front({nr,nc});
				}
				else{
					depth[nr][nc] = depth[r][c]+1;
					dq.push_back({nr,nc});
				}
			}
		}
	}
	cout<<ans;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 129112 KB Output is correct
2 Correct 17 ms 126812 KB Output is correct
3 Correct 17 ms 129104 KB Output is correct
4 Correct 22 ms 129572 KB Output is correct
5 Correct 18 ms 129116 KB Output is correct
6 Correct 17 ms 126960 KB Output is correct
7 Correct 17 ms 129116 KB Output is correct
8 Correct 19 ms 129116 KB Output is correct
9 Correct 18 ms 129024 KB Output is correct
10 Correct 18 ms 129116 KB Output is correct
11 Correct 18 ms 129112 KB Output is correct
12 Correct 20 ms 129116 KB Output is correct
13 Correct 18 ms 129132 KB Output is correct
14 Correct 18 ms 129116 KB Output is correct
15 Correct 24 ms 129112 KB Output is correct
16 Correct 26 ms 129368 KB Output is correct
17 Correct 25 ms 129160 KB Output is correct
18 Correct 21 ms 129624 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 141656 KB Output is correct
2 Correct 49 ms 133208 KB Output is correct
3 Correct 257 ms 141396 KB Output is correct
4 Correct 84 ms 135312 KB Output is correct
5 Correct 169 ms 139384 KB Output is correct
6 Correct 603 ms 169056 KB Output is correct
7 Correct 19 ms 141396 KB Output is correct
8 Correct 22 ms 141384 KB Output is correct
9 Correct 18 ms 127068 KB Output is correct
10 Correct 17 ms 126812 KB Output is correct
11 Correct 19 ms 141264 KB Output is correct
12 Correct 17 ms 129116 KB Output is correct
13 Correct 52 ms 133080 KB Output is correct
14 Correct 39 ms 131248 KB Output is correct
15 Correct 37 ms 131244 KB Output is correct
16 Correct 31 ms 129176 KB Output is correct
17 Correct 121 ms 135252 KB Output is correct
18 Correct 91 ms 135320 KB Output is correct
19 Correct 90 ms 135248 KB Output is correct
20 Correct 73 ms 135508 KB Output is correct
21 Correct 151 ms 139392 KB Output is correct
22 Correct 179 ms 139420 KB Output is correct
23 Correct 189 ms 137348 KB Output is correct
24 Correct 176 ms 139388 KB Output is correct
25 Correct 449 ms 141392 KB Output is correct
26 Correct 331 ms 241708 KB Output is correct
27 Correct 454 ms 194672 KB Output is correct
28 Correct 577 ms 168704 KB Output is correct
29 Correct 559 ms 165664 KB Output is correct
30 Correct 516 ms 177156 KB Output is correct
31 Correct 426 ms 142332 KB Output is correct
32 Correct 408 ms 172168 KB Output is correct