oj.uz

Submission #1032554

# Submission time Handle Problem Language Result Execution time Memory
1032554 2024-07-24T02:14:13 Z hippo123 Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 641 ms 138492 KB 
#include <bits/stdc++.h>
 
using namespace std;
#define ll long long
#define pr pair<int, int>
#define f first
#define s second
#define pb push_back
const int ndim=4001;
int ns;
string mps[ndim];
vector<vector<int>> level(ndim, vector<int> (ndim, -1));



int h, w; 

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

bool check(int x, int y){
	if(x>=0 && x<h && y>=0 && y<w && mps[x][y]!='.') return true;
	else return false; 
}

int main(){
	cin>>h>>w;
	for (int i=0; i<h; i++) cin>>mps[i];

	deque<pr> q; 
	q.push_front({0, 0}); // x, y
	level[0][0]=1;
	int ans=0;
	while(!q.empty()){
		pr nd=q.front(); q.pop_front();
		ans=max(ans, level[nd.f][nd.s]);
		for (int i=0; i<4; i++){
			int x=nd.f+dx[i]; int y=nd.s+dy[i];
			if(check(x, y) && level[x][y]==-1){
				if(mps[x][y]==mps[nd.f][nd.s]){
					q.push_front({x, y}); 
					level[x][y]=level[nd.f][nd.s];					
				}
				else{
					q.push_back({x, y}); 
					level[x][y]=level[nd.f][nd.s]+1;
				}
			}
		}
	}
	cout<<ans<<endl;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 64080 KB Output is correct
2 Correct 33 ms 63324 KB Output is correct
3 Correct 30 ms 63312 KB Output is correct
4 Correct 37 ms 63836 KB Output is correct
5 Correct 34 ms 63316 KB Output is correct
6 Correct 30 ms 63320 KB Output is correct
7 Correct 30 ms 63320 KB Output is correct
8 Correct 38 ms 63324 KB Output is correct
9 Correct 30 ms 63316 KB Output is correct
10 Correct 32 ms 63324 KB Output is correct
11 Correct 31 ms 63316 KB Output is correct
12 Correct 32 ms 63580 KB Output is correct
13 Correct 32 ms 63316 KB Output is correct
14 Correct 32 ms 63312 KB Output is correct
15 Correct 45 ms 63908 KB Output is correct
16 Correct 40 ms 63924 KB Output is correct
17 Correct 39 ms 63828 KB Output is correct
18 Correct 38 ms 63832 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 63312 KB Output is correct
2 Correct 71 ms 67156 KB Output is correct
3 Correct 381 ms 109044 KB Output is correct
4 Correct 115 ms 73964 KB Output is correct
5 Correct 199 ms 83284 KB Output is correct
6 Correct 641 ms 122604 KB Output is correct
7 Correct 40 ms 63316 KB Output is correct
8 Correct 36 ms 63344 KB Output is correct
9 Correct 31 ms 63320 KB Output is correct
10 Correct 31 ms 63312 KB Output is correct
11 Correct 31 ms 63324 KB Output is correct
12 Correct 31 ms 63324 KB Output is correct
13 Correct 72 ms 67156 KB Output is correct
14 Correct 55 ms 65936 KB Output is correct
15 Correct 49 ms 66136 KB Output is correct
16 Correct 51 ms 64596 KB Output is correct
17 Correct 144 ms 74836 KB Output is correct
18 Correct 109 ms 74744 KB Output is correct
19 Correct 116 ms 74068 KB Output is correct
20 Correct 101 ms 73256 KB Output is correct
21 Correct 207 ms 84052 KB Output is correct
22 Correct 228 ms 83284 KB Output is correct
23 Correct 242 ms 80212 KB Output is correct
24 Correct 217 ms 83960 KB Output is correct
25 Correct 358 ms 108880 KB Output is correct
26 Correct 394 ms 138492 KB Output is correct
27 Correct 527 ms 135444 KB Output is correct
28 Correct 615 ms 122604 KB Output is correct
29 Correct 622 ms 121028 KB Output is correct
30 Correct 575 ms 125928 KB Output is correct
31 Correct 431 ms 85792 KB Output is correct
32 Correct 470 ms 124196 KB Output is correct