Submission #946532

#	Time	Username	Problem	Language	Result	Execution time	Memory
946532		NintsiChkhaidze	Tracks in the Snow (BOI13_tracks)	C++17	8.85 / 100	2062 ms	190656 KiB

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.666666666666667 / 30
• Subtask 2: 2.1875 / 70