oj.uz

Submission #946531

# Submission time Handle Problem Language Result Execution time Memory
946531 2024-03-14T18:11:42 Z NintsiChkhaidze Tracks in the Snow (BOI13_tracks) C++17
6.66667 / 100
 158 ms 14676 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 = 1000 + 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;
	
	priority_queue <pair<int,pii>> pq;
	d[1][1] = 1;
	pq.push({-1,{1,1}});

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

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

			if (a[x][y] != a[X][Y]) w = 1;
			if (d[X][Y] > D + w){
				d[X][Y] = D + w;
				pq.push({-D-w,{X,Y}});
			}
		}
	}

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

Subtask #1
6.66666666667 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 40 ms 5212 KB Output isn't correct
2 Incorrect 1 ms 2392 KB Output isn't correct
3 Incorrect 2 ms 4560 KB Output isn't correct
4 Correct 25 ms 5412 KB Output is correct
5 Incorrect 13 ms 4700 KB Output isn't correct
6 Incorrect 1 ms 2396 KB Output isn't correct
7 Incorrect 1 ms 4700 KB Output isn't correct
8 Correct 2 ms 4700 KB Output is correct
9 Incorrect 2 ms 4700 KB Output isn't correct
10 Incorrect 11 ms 5148 KB Output isn't correct
11 Correct 7 ms 4956 KB Output is correct
12 Incorrect 15 ms 4696 KB Output isn't correct
13 Incorrect 13 ms 4700 KB Output isn't correct
14 Incorrect 13 ms 4700 KB Output isn't correct
15 Incorrect 50 ms 6488 KB Output isn't correct
16 Incorrect 40 ms 5212 KB Output isn't correct
17 Incorrect 40 ms 5212 KB Output isn't correct
18 Correct 25 ms 5400 KB Output is correct

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 10584 KB Execution killed with signal 11
2 Runtime error 16 ms 11868 KB Execution killed with signal 11
3 Runtime error 40 ms 14584 KB Execution killed with signal 11
4 Runtime error 24 ms 12892 KB Execution killed with signal 11
5 Runtime error 30 ms 13648 KB Execution killed with signal 11
6 Runtime error 39 ms 14448 KB Execution killed with signal 11
7 Runtime error 5 ms 10588 KB Execution killed with signal 11
8 Runtime error 5 ms 10588 KB Execution killed with signal 11
9 Incorrect 3 ms 2652 KB Output isn't correct
10 Incorrect 2 ms 2576 KB Output isn't correct
11 Runtime error 5 ms 10588 KB Execution killed with signal 11
12 Incorrect 4 ms 4956 KB Output isn't correct
13 Runtime error 16 ms 11864 KB Execution killed with signal 11
14 Incorrect 141 ms 13500 KB Output isn't correct
15 Incorrect 158 ms 13892 KB Output isn't correct
16 Incorrect 70 ms 6856 KB Output isn't correct
17 Runtime error 22 ms 12636 KB Execution killed with signal 11
18 Runtime error 23 ms 12624 KB Execution killed with signal 11
19 Runtime error 23 ms 12884 KB Execution killed with signal 11
20 Runtime error 22 ms 12624 KB Execution killed with signal 11
21 Runtime error 30 ms 13648 KB Execution killed with signal 11
22 Runtime error 31 ms 13684 KB Execution killed with signal 11
23 Runtime error 31 ms 13660 KB Execution killed with signal 11
24 Runtime error 32 ms 13396 KB Execution killed with signal 11
25 Runtime error 43 ms 14676 KB Execution killed with signal 11
26 Runtime error 39 ms 14080 KB Execution killed with signal 11
27 Runtime error 40 ms 14416 KB Execution killed with signal 11
28 Runtime error 39 ms 14416 KB Execution killed with signal 11
29 Runtime error 39 ms 14420 KB Execution killed with signal 11
30 Runtime error 40 ms 14492 KB Execution killed with signal 11
31 Runtime error 33 ms 13792 KB Execution killed with signal 11
32 Runtime error 38 ms 14420 KB Execution killed with signal 11