oj.uz

Submission #946548

# Submission time Handle Problem Language Result Execution time Memory
946548 2024-03-14T18:23:53 Z NintsiChkhaidze Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 640 ms 146568 KB 
#include <bits/stdc++.h>
#define ll long long
#define s second
#define f first
#define pb push_back
#define pii pair <int,int>
#define left (h<<1),l,(l + r)/2
#define right ((h<<1)|1),(l + r)/2 + 1,r
using namespace std;

const int N = 4000 + 3,inf = 1e9;
char a[N][N];
int d[N][N];
vector <pii> neighbours = {{0,1}, {0,-1}, {1,0}, {-1,0}};

signed main(){
	ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);

	int n,m;
	cin>>n>>m;

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			cin >> a[i][j],d[i][j] = inf;
	
	deque <pair<int,pii>> pq;
	d[1][1] = 1;
	pq.pb({1,{1,1}});

	while (pq.size()){
		int D = pq.front().f,x = pq.front().s.f,y = pq.front().s.s;
		pq.pop_front();
		if (d[x][y] != D) continue;

		for (auto [dx,dy]: neighbours){
			int X = dx + x,Y = dy + y;
			if (X < 1 || X > n || Y < 1 || Y > m || a[X][Y] == '.') continue;
			int w = (a[x][y] != a[X][Y]);

			if (w == 1 && d[X][Y] > D + w){
				d[X][Y] = D + w;
				pq.pb({D+w,{X,Y}});
			}
			
			if (!w && d[X][Y] > D){
				d[X][Y] = D;
				pq.push_front({D,{X,Y}});
			}
		}
	}

	int ans = 0;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			if (a[i][j] != '.') ans=max(ans,d[i][j]);
	cout<<ans;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12888 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 8 ms 12892 KB Output is correct
5 Correct 4 ms 10588 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4440 KB Output is correct
10 Correct 3 ms 6492 KB Output is correct
11 Correct 2 ms 6748 KB Output is correct
12 Correct 6 ms 10588 KB Output is correct
13 Correct 3 ms 10792 KB Output is correct
14 Correct 3 ms 10588 KB Output is correct
15 Correct 11 ms 12880 KB Output is correct
16 Correct 14 ms 12892 KB Output is correct
17 Correct 9 ms 12636 KB Output is correct
18 Correct 7 ms 12888 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 78428 KB Output is correct
2 Correct 43 ms 27224 KB Output is correct
3 Correct 268 ms 78724 KB Output is correct
4 Correct 71 ms 41624 KB Output is correct
5 Correct 156 ms 62036 KB Output is correct
6 Correct 640 ms 98556 KB Output is correct
7 Correct 10 ms 78684 KB Output is correct
8 Correct 9 ms 78428 KB Output is correct
9 Correct 2 ms 4700 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 9 ms 78428 KB Output is correct
12 Correct 1 ms 6492 KB Output is correct
13 Correct 43 ms 27224 KB Output is correct
14 Correct 31 ms 21084 KB Output is correct
15 Correct 24 ms 23268 KB Output is correct
16 Correct 21 ms 10844 KB Output is correct
17 Correct 107 ms 43696 KB Output is correct
18 Correct 75 ms 43660 KB Output is correct
19 Correct 75 ms 41620 KB Output is correct
20 Correct 72 ms 37508 KB Output is correct
21 Correct 173 ms 64220 KB Output is correct
22 Correct 156 ms 62036 KB Output is correct
23 Correct 211 ms 53840 KB Output is correct
24 Correct 152 ms 64132 KB Output is correct
25 Correct 428 ms 78816 KB Output is correct
26 Correct 458 ms 146568 KB Output is correct
27 Correct 520 ms 105976 KB Output is correct
28 Correct 607 ms 98364 KB Output is correct
29 Correct 637 ms 94916 KB Output is correct
30 Correct 574 ms 104384 KB Output is correct
31 Correct 498 ms 66968 KB Output is correct
32 Correct 480 ms 103608 KB Output is correct