Submission #720783

#	Time	Username	Problem	Language	Result	Execution time	Memory
720783		Lextyle	Tracks in the Snow (BOI13_tracks)	C++17	73.65 / 100	758 ms	119680 KiB

tracks

#include <bits/stdc++.h>
#pragma warning(disable : 4996)
#pragma warning(disable : 6031)
#define USACO freopen("exercise.in", "r", stdin); freopen("exercise.out", "w+", stdout)
#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define ll long long
using namespace std;

ll binpow(ll a, ll x, ll m) {
	ll ans = 1, md = a % m;
	while (x != 0) {
		if (x % 2 == 1) ans = (ans * md) % m;
		md = (md * md) % m;
		x >>= 1;
	}
	return ans;
}
ll gcd(ll a, ll b) {
	return b == 0 ? a : gcd(b, a % b);
}
ll lcm(ll a, ll b) {
	return a * b / gcd(a, b);
}
bool ok(int r, int c, int n, int m) {
	return r >= 0 && r < n && c >= 0 && c < m;
}
/*
*/
char a[4000][4000];
int d[4000][4000];

void solve() {
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) cin >> a[i][j];
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) d[i][j] = INT32_MAX;
	}
	d[0][0] = 0;
	deque<pair<int, int>> s;
	s.push_front({ 0, 0 });
	while (!s.empty()) {
		int r = s.front().first, c = s.front().second;
		s.pop_front();
		if (ok(r - 1, c, n, m) && a[r - 1][c] != '.' && d[r][c] + (a[r][c] != a[r - 1][c]) < d[r - 1][c]) {
			d[r - 1][c] = d[r][c] + (a[r][c] != a[r - 1][c]);
			if (a[r][c] != a[r - 1][c]) s.push_back({ r - 1, c });
			else s.push_front({ r - 1, c });
		}
		if (ok(r + 1, c, n, m) && a[r + 1][c] != '.' && d[r][c] + (a[r][c] != a[r + 1][c]) < d[r + 1][c]) {
			d[r + 1][c] = d[r][c] + (a[r][c] != a[r + 1][c]);
			if (a[r][c] != a[r + 1][c]) s.push_back({ r + 1, c });
			else s.push_front({ r + 1, c });
		}
		if (ok(r, c - 1, n, m) && a[r][c - 1] != '.' && d[r][c] + (a[r][c] != a[r][c - 1]) < d[r][c - 1]) {
			d[r][c - 1] = d[r][c] + (a[r][c] != a[r][c - 1]);
			if (a[r][c] != a[r][c - 1]) s.push_back({ r, c - 1 });
			else s.push_front({ r, c - 1 });
		}
		if (ok(r, c + 1, n, m) && a[r][c + 1] != '.' && d[r][c] + (a[r][c] != a[r][c + 1]) < d[r][c + 1]) {
			d[r][c + 1] = d[r][c] + (a[r][c] != a[r][c + 1]);
			if (a[r][c] != a[r][c + 1]) s.push_back({ r, c + 1 });
			else s.push_front({ r, c + 1 });
		}
	}
	int mx = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (a[i][j] != '.') mx = max(mx, d[i][j]);
		}
	}
	cout << mx + 1 << "\n";
}

int main() {
	//USACO;
	fastIO;
	solve();
}

Compilation message (stderr)

tracks.cpp:2: warning: ignoring '#pragma warning ' [-Wunknown-pragmas]
    2 | #pragma warning(disable : 4996)
      | 
tracks.cpp:3: warning: ignoring '#pragma warning ' [-Wunknown-pragmas]
    3 | #pragma warning(disable : 6031)
      |

• Subtask 1: 23.333333333333332 / 30
• Subtask 2: 50.3125 / 70