Submission #1126187

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126187		WH8	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	1652 ms	509604 KiB

tracks

#include <bits/stdc++.h>
using namespace std;
#define iloop(x, n) for (long long i = x; i < n; ++i)
#define jloop(x, n) for (long long j = x; j < n; ++j)
#define kloop(x, n) for (long long k = x; k < n; ++k)
#define dloop(x, n) for (long long d = x; d >= n; --d)
#define ll long long
#define pll pair<long long, long long>
#define pii pair<int, int>
#define iii tuple<int, int, int>
#define vi vector<int>
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define int long long
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
#define dg(x) cout << #x << ": " << x << endl
#define all(x) x.begin(), x.end()
#define flag cout << "HERE" << endl;
#define FASTIO               \
    ios::sync_with_stdio(false); \
	cin.tie(0);              \
    cout.tie(0);
#define prt(x) \
    cout << "Vector " << #x << endl << ":"; \
    for (auto it : x) cout << it << " "; \
    cout << endl;
#define ppr(x) \
    cout << "Pair " << #x << endl << ":";\
    cout << x.first << " " << x.second << endl;

signed main(){
	int h, w; cin >> h >> w;
	char mat[h][w]; 
	int dp[h][w];
	iloop(0, h){
		jloop(0, w){
			cin >> mat[i][j];
			dp[i][j] = -1;
		}
	}
	dp[0][0] = 0;
	int ans = 0;
	deque<pair<pll, pll>> dq; // to, from
	dq.push_back({{0, 0}, {0, 0}});
	int dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
	while (!dq.empty()){
		auto cur = dq.front().f, from = dq.front().s;
		dq.pop_front();
		if (dp[cur.f][cur.s] != -1 and !(cur.f == 0 and cur.s == 0)) continue;
		dp[cur.f][cur.s] = dp[from.f][from.s] + (mat[cur.f][cur.s] != mat[from.f][from.s]);
		ans = max(ans, dp[cur.f][cur.s]);
		iloop(0, 4){
			int nx = cur.f + dir[i][0], ny = cur.s + dir[i][1];
			if (nx < 0 or nx >= h or ny < 0 or ny >= w or mat[nx][ny] == '.' or dp[nx][ny] != -1) continue;
			if (mat[cur.f][cur.s] == mat[from.f][from.s]){
				dq.push_front({{nx, ny}, cur});
			}
			else dq.push_back({{nx, ny}, cur});
		}
	}
	/*iloop(0, h){
		jloop(0, w){
			cout << dp[i][j];
		}
		cout << endl;
	}*/
	cout << ans + 1;
}

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