Submission #1216248

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216248		A_M_Namdar	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	874 ms	96272 KiB

tracks

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

const int N = 4000;
int n, m, a[N][N], cnt;
queue<pair<int, int>> q[5];
bool mark[N][N];
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, -1, 1};

bool is_valid(int x, int y) {
	return x >= 0 && y >= 0 && x < n && y < m && !mark[x][y];
}

void add_adj(int x, int y) {
	if (mark[x][y]) return;
	cnt++;
	mark[x][y] = true;
	for (int i = 0; i < 4; i++) {
		int X = x + dx[i], Y = y + dy[i];
		if (is_valid(X, Y)) 
			q[a[X][Y]].push({X, Y});
	}
}

void input() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		for (int j = 0; j < m; j++) 
			a[i][j] = 2 * (s[j] == '.') + (s[j] == 'F');
	}
}

void solve() {
	q[a[0][0]].push({0, 0});
	int ans = 0;
	for (int i = 0; i < n; i++) 
		for (int j = 0; j < m; j++) 
			if (a[i][j] == 2) {
				mark[i][j] = true;
				cnt++;
			}
	for (int i = 0; cnt < n * m; i ^= 1) {
		int b = a[0][0] ^ i;
		while (!q[b].empty()) {
			add_adj(q[b].front().first, q[b].front().second);
			q[b].pop();
		}
		ans++;
	}
	cout << ans;
}

int main() {
	ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
	input();
	solve();
}

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