Submission #793050

# Submission time Handle Problem Language Result Execution time Memory
793050 2023-07-25T13:01:58 Z MODDI Tracks in the Snow (BOI13_tracks) C++14
100 / 100
566 ms 132488 KB
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<long long, long long> pll;
using namespace std;
int n, m;
vector<string> mat;
bool vis[4001][4001];
int dist[4001][4001], dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
bool in_range(int i, int j){
	if(i >= 0 && j >= 0 && i < n && j < m)	return true;
	return false;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>m;
	mat.resize(n);
	for(int i = 0; i < n; i++)
		cin>>mat[i];
	
	deque<pii> q;
	q.push_front(mp(0,0));
	int ans = 1;
	dist[0][0] = vis[0][0] = 1;
	while(!q.empty()){
		pii at = q.front();
		q.pop_front();
		ans = max(ans, dist[at.first][at.second]);
		for(int dir = 0; dir < 4; dir++){
			int nx = at.first + dx[dir], ny = at.second + dy[dir];
			if(in_range(nx, ny) && mat[nx][ny] != '.' && !vis[nx][ny]){
				vis[nx][ny] = true;
				dist[nx][ny] = dist[at.first][at.second] + (mat[at.first][at.second] != mat[nx][ny]);
				if(mat[at.first][at.second] != mat[nx][ny])	q.pb(mp(nx,ny));
				else q.push_front(mp(nx,ny));
				//q.push(mp(-dist[nx][ny], mp(nx,ny)));
			}
		}
	}
	cout<<ans<<endl;
}
# Verdict Execution time Memory Grader output
1 Correct 13 ms 5460 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 7 ms 5204 KB Output is correct
5 Correct 2 ms 2900 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 0 ms 724 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 1108 KB Output is correct
10 Correct 2 ms 2524 KB Output is correct
11 Correct 3 ms 2132 KB Output is correct
12 Correct 6 ms 3028 KB Output is correct
13 Correct 2 ms 2900 KB Output is correct
14 Correct 2 ms 2900 KB Output is correct
15 Correct 8 ms 5204 KB Output is correct
16 Correct 10 ms 5460 KB Output is correct
17 Correct 7 ms 5204 KB Output is correct
18 Correct 8 ms 5232 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 15 ms 30932 KB Output is correct
2 Correct 33 ms 15180 KB Output is correct
3 Correct 144 ms 75488 KB Output is correct
4 Correct 66 ms 32924 KB Output is correct
5 Correct 87 ms 54284 KB Output is correct
6 Correct 509 ms 110412 KB Output is correct
7 Correct 16 ms 32232 KB Output is correct
8 Correct 15 ms 30860 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 16 ms 31656 KB Output is correct
12 Correct 1 ms 1620 KB Output is correct
13 Correct 41 ms 15180 KB Output is correct
14 Correct 18 ms 10500 KB Output is correct
15 Correct 17 ms 13140 KB Output is correct
16 Correct 15 ms 5768 KB Output is correct
17 Correct 78 ms 29012 KB Output is correct
18 Correct 63 ms 36072 KB Output is correct
19 Correct 55 ms 32988 KB Output is correct
20 Correct 38 ms 25812 KB Output is correct
21 Correct 114 ms 53608 KB Output is correct
22 Correct 90 ms 54328 KB Output is correct
23 Correct 152 ms 44756 KB Output is correct
24 Correct 89 ms 50764 KB Output is correct
25 Correct 355 ms 96392 KB Output is correct
26 Correct 311 ms 132488 KB Output is correct
27 Correct 427 ms 130896 KB Output is correct
28 Correct 554 ms 110416 KB Output is correct
29 Correct 566 ms 107988 KB Output is correct
30 Correct 479 ms 113664 KB Output is correct
31 Correct 371 ms 74528 KB Output is correct
32 Correct 394 ms 118204 KB Output is correct