oj.uz

Submission #961998

# Submission time Handle Problem Language Result Execution time Memory
961998 2024-04-13T02:22:19 Z pcc Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 494 ms 163584 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>
#define tiii tuple<int,int,int>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,popcnt,sse4")

const int mxn = 4040;
int N,M;
string arr[mxn];
int dist[mxn][mxn];
deque<tiii> dq;
pii dir[] = {{0,1},{0,-1},{1,0},{-1,0}};

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	memset(dist,-1,sizeof(dist));
	cin>>N>>M;
	for(int i = 1;i<=N;i++){
		cin>>arr[i];
		arr[i] = "."+arr[i]+".";
	}
	arr[0] = arr[N+1] = string(M+2,'.');
	dist[1][1] = 1;
	dq.push_back(tiii(1,1,1));
	while(!dq.empty()){
		auto [r,c,d] = dq.front();
		dq.pop_front();
		if(dist[r][c] != d)continue;
		for(auto &dd:dir){
			int nr = r+dd.fs,nc = c+dd.sc;
			if(arr[nr][nc] == '.')continue;
			int nd = d+(arr[nr][nc] != arr[r][c]);
			if(dist[nr][nc] == -1||dist[nr][nc]>nd){
				dist[nr][nc] = nd;
				if(nd != d)dq.push_back(tiii(nr,nc,dist[nr][nc]));
				else dq.push_front(tiii(nr,nc,dist[nr][nc]));
			}
		}
	}
	int ans = 0;
	for(int i = 1;i<=N;i++){
		for(int j = 1;j<=M;j++)ans = max(ans,dist[i][j]);
	}
	cout<<ans<<'\n';
	return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 64860 KB Output is correct
2 Correct 9 ms 64348 KB Output is correct
3 Correct 9 ms 64348 KB Output is correct
4 Correct 13 ms 65084 KB Output is correct
5 Correct 10 ms 64604 KB Output is correct
6 Correct 9 ms 64356 KB Output is correct
7 Correct 10 ms 64344 KB Output is correct
8 Correct 9 ms 64348 KB Output is correct
9 Correct 9 ms 64348 KB Output is correct
10 Correct 10 ms 64564 KB Output is correct
11 Correct 10 ms 64860 KB Output is correct
12 Correct 12 ms 64600 KB Output is correct
13 Correct 11 ms 64604 KB Output is correct
14 Correct 10 ms 64604 KB Output is correct
15 Correct 16 ms 64860 KB Output is correct
16 Correct 16 ms 64860 KB Output is correct
17 Correct 13 ms 64856 KB Output is correct
18 Correct 13 ms 64860 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 64348 KB Output is correct
2 Correct 33 ms 67420 KB Output is correct
3 Correct 126 ms 95876 KB Output is correct
4 Correct 51 ms 71872 KB Output is correct
5 Correct 85 ms 82012 KB Output is correct
6 Correct 443 ms 115664 KB Output is correct
7 Correct 10 ms 64348 KB Output is correct
8 Correct 10 ms 64348 KB Output is correct
9 Correct 10 ms 64604 KB Output is correct
10 Correct 19 ms 64348 KB Output is correct
11 Correct 10 ms 64348 KB Output is correct
12 Correct 9 ms 64280 KB Output is correct
13 Correct 32 ms 67420 KB Output is correct
14 Correct 22 ms 66392 KB Output is correct
15 Correct 20 ms 66480 KB Output is correct
16 Correct 21 ms 65628 KB Output is correct
17 Correct 78 ms 72504 KB Output is correct
18 Correct 59 ms 72424 KB Output is correct
19 Correct 49 ms 71656 KB Output is correct
20 Correct 41 ms 71260 KB Output is correct
21 Correct 87 ms 82780 KB Output is correct
22 Correct 86 ms 82148 KB Output is correct
23 Correct 141 ms 79704 KB Output is correct
24 Correct 74 ms 82268 KB Output is correct
25 Correct 306 ms 95884 KB Output is correct
26 Correct 448 ms 163584 KB Output is correct
27 Correct 404 ms 122976 KB Output is correct
28 Correct 494 ms 115152 KB Output is correct
29 Correct 452 ms 112048 KB Output is correct
30 Correct 449 ms 121092 KB Output is correct
31 Correct 312 ms 85204 KB Output is correct
32 Correct 460 ms 120892 KB Output is correct