Submission #855406

#	Time	Username	Problem	Language	Result	Execution time	Memory
855406		dayalk	Tracks in the Snow (BOI13_tracks)	C++17	6.04 / 100	869 ms	131400 KiB

tracks

#include <bits/stdc++.h>
#define mod 1000000007
#define init(arr, val) memset(arr, val, sizeof(arr))
#define fr(a,b) for(ll i = a; i < b; i++)
#define loop(i, a, b) for (ll i = a; i < b; i++)
#define loopr(i, a, b) for (ll i = a; i >= b; i--)
#define loops(i, a, b, step) for (ll i = a; i < b; i += step)
#define looprs(i, a, b, step) for (ll i = a; i >= b; i -= step)
#define ull unsigned long long int
#define ll long long int
#define P pair
#define pll pair<long long, long long>
#define pii pair<int, int>
#define pli pair<ll, int>
#define pil pair<int, ll>
#define PUU pair<unsigned long long int, unsigned long long int>
#define L list
#define V vector
#define D deque
#define ST set
#define MS multiset
#define M map
#define UM unordered_map
#define mp make_pair
#define pb push_back
#define pf push_front
#define MM multimap
#define F first
#define S second
#define IT iterator
#define RIT reverse_iterator
#define fast_io                       \
	ios_base::sync_with_stdio(false); \
	cin.tie();                        \
	cout.tie()
#define FILE_READ_IN freopen("input.txt", "r", stdin);
#define FILE_READ_OUT freopen("output.txt", "w", stdout);
#define prDouble(x) cout << fixed << setprecision(10) << x
#define all(a) a.begin(), a.end()
#define ld long double
#define inf (1LL<<60)
using namespace std;
const ll maxn = 2e5 + 1;
const double pi = acos(-1);

vector<pii> dir = { {1,0}, {0,1}, {0, -1}, {-1, 0} };

int main() {
	fast_io;
	int tests = 1;
	// cin >> tests;
	for (int test_case = 1; test_case <= tests; test_case++) {
		int h, w; cin >> h >> w;
		char a[h][w];
		fr(0, h) {
			loop(j, 0, w) cin >> a[i][j];
		}
		vector<int> d(h * w, 1e9);
		d[(h - 1) * w] = 0;
		deque<pair<int, int>> q;
		q.push_back(make_pair(h - 1, 0));
		int res = 0;
		while (!q.empty()) {
			auto cur = q.front();
			int curf = cur.first;
			int curs = cur.second;
			q.pop_front();
			auto dis = d[curf * w + curs];
			for (auto i : dir) {
				// pii j = cur + i;
				int jf = curf + i.first;
				int js = curs + i.second;
				if (jf < 0) continue;
				if (jf >= h) continue;
				if (js < 0) continue;
				if (js >= w) continue;
				int e = 0;
				// if (a[curf][curs] != '.') {
				e = (a[curf][curs] != a[jf][js]);
				// }
				if (dis + e < d[jf * w + js]) {
					d[jf * w + js] = dis + e;
					if (e == 0) q.push_front({ jf,js });
					else q.push_back({ jf,js });
				}
			}
		}
		fr(0, h * w) {
			if (a[i / w][i % w]) res = max(res, d[i]);
		}
		cout << res << endl;
	}
	return 0;
}

• Subtask 1: 1.6666666666666667 / 30
• Subtask 2: 4.375 / 70