Submission #401795

#	Time	Username	Problem	Language	Result	Execution time	Memory
401795		jli12345	Tracks in the Snow (BOI13_tracks)	C++11	82.50 / 100	2109 ms	164076 KiB

tracks

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;
#define f first
#define s second


int N, M;
char arr[4100][4100];

int depth[4100][4100];

struct comp{
	bool operator()(const pair<pii, int> &a, const pair<pii, int> &b){
		return a.s > b.s;
	}
};

int xd[4] = {1, -1, 0, 0};
int yd[4] = {0, 0, 1, -1};

int main(){
	cin >> N >> M;
	for (int i = 1; i <= N; i++){
		for (int j = 1; j <= M; j++){
			cin >> arr[i][j];
		}
	}
	priority_queue<pair<pii, int>, vector<pair<pii, int> >, comp> pq;
	pq.push({{1, 1}, 1});
	depth[1][1] = 1;
	while (!pq.empty()){
		int x = pq.top().f.f;
		int y = pq.top().f.s;
		int w = pq.top().s;
		pq.pop();
		//if (depth[x][y] >= w) continue;
		for (int i = 0; i < 4; i++){
			int nx = x+xd[i];
			int ny = y+yd[i];
			if (nx >= 1 && nx <= N && ny >= 1 && ny <= M && arr[nx][ny] != '.' && !depth[nx][ny]){
				if (arr[x][y] == arr[nx][ny])
					depth[nx][ny] = depth[x][y];
				else
					depth[nx][ny] = depth[x][y]+1;
				pq.push({{nx, ny}, depth[nx][ny]});
			}
		}
	}
	int ans = 0;
	for (int i = 1; i <= N; i++){
		for (int j = 1; j <= M; j++){
			ans = max(ans, depth[i][j]);
		}
	}
	cout << ans << "\n";
}

Compilation message (stderr)

tracks.cpp: In function 'int main()':
tracks.cpp:36:7: warning: unused variable 'w' [-Wunused-variable]
   36 |   int w = pq.top().s;
      |       ^

• Subtask 1: 30 / 30
• Subtask 2: 52.5 / 70