Submission #946548

#	Time	Username	Problem	Language	Result	Execution time	Memory
946548		NintsiChkhaidze	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	640 ms	146568 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;
	
	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 / 30
• Subtask 2: 70 / 70