Submission #946532

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
946532	2024-03-14T18:12:01 Z	NintsiChkhaidze	Tracks in the Snow (BOI13_tracks)	C++17	8.85417 / 100	2000 ms	190656 KB

tracks

#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;
	
	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	42 ms	12892 KB	Output isn't correct
2	Incorrect	1 ms	4444 KB	Output isn't correct
3	Incorrect	1 ms	4444 KB	Output isn't correct
4	Correct	26 ms	13340 KB	Output is correct
5	Incorrect	14 ms	10844 KB	Output isn't correct
6	Incorrect	1 ms	4444 KB	Output isn't correct
7	Incorrect	1 ms	4444 KB	Output isn't correct
8	Correct	1 ms	4444 KB	Output is correct
9	Incorrect	2 ms	4440 KB	Output isn't correct
10	Incorrect	11 ms	7196 KB	Output isn't correct
11	Correct	7 ms	6676 KB	Output is correct
12	Incorrect	18 ms	10884 KB	Output isn't correct
13	Incorrect	14 ms	10844 KB	Output isn't correct
14	Incorrect	14 ms	10844 KB	Output isn't correct
15	Incorrect	46 ms	13656 KB	Output isn't correct
16	Incorrect	41 ms	12892 KB	Output isn't correct
17	Incorrect	43 ms	12892 KB	Output isn't correct
18	Correct	28 ms	13340 KB	Output is correct

Subtask #2

2.1875 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	16 ms	78684 KB	Output isn't correct
2	Incorrect	252 ms	34632 KB	Output isn't correct
3	Execution timed out	2013 ms	141196 KB	Time limit exceeded
4	Incorrect	575 ms	43692 KB	Output isn't correct
5	Incorrect	1436 ms	168028 KB	Output isn't correct
6	Execution timed out	2017 ms	116792 KB	Time limit exceeded
7	Incorrect	15 ms	78684 KB	Output isn't correct
8	Incorrect	17 ms	78744 KB	Output isn't correct
9	Incorrect	9 ms	4956 KB	Output isn't correct
10	Incorrect	4 ms	2908 KB	Output isn't correct
11	Incorrect	13 ms	78428 KB	Output isn't correct
12	Incorrect	5 ms	6940 KB	Output isn't correct
13	Incorrect	259 ms	34236 KB	Output isn't correct
14	Incorrect	143 ms	29108 KB	Output isn't correct
15	Incorrect	154 ms	30656 KB	Output isn't correct
16	Incorrect	109 ms	14768 KB	Output isn't correct
17	Incorrect	643 ms	71900 KB	Output isn't correct
18	Incorrect	649 ms	70604 KB	Output isn't correct
19	Incorrect	579 ms	43592 KB	Output isn't correct
20	Incorrect	494 ms	52728 KB	Output isn't correct
21	Incorrect	1384 ms	96196 KB	Output isn't correct
22	Incorrect	1424 ms	166692 KB	Output isn't correct
23	Incorrect	1272 ms	109496 KB	Output isn't correct
24	Incorrect	1332 ms	120676 KB	Output isn't correct
25	Execution timed out	2039 ms	190656 KB	Time limit exceeded
26	Correct	1387 ms	80784 KB	Output is correct
27	Execution timed out	2057 ms	93732 KB	Time limit exceeded
28	Execution timed out	2043 ms	115348 KB	Time limit exceeded
29	Execution timed out	2037 ms	104232 KB	Time limit exceeded
30	Execution timed out	2049 ms	102280 KB	Time limit exceeded
31	Incorrect	1843 ms	73808 KB	Output isn't correct
32	Execution timed out	2062 ms	92284 KB	Time limit exceeded