Submission #1187784

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187784		Tsagana	Tracks in the Snow (BOI13_tracks)	C++20	97.81 / 100	704 ms	1114112 KiB

tracks

#include<bits/stdc++.h>

#define IOS ios_base::sync_with_stdio(false);cin.tie();cout.tie();
#define all(x) x.begin(), x.end()
#define int long long
#define pq priority_queue
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define pp pop_back
#define F first
#define S second

using namespace std;

int n, m, ans;
string g[4010];
vector<array<int, 2>> v[2];
int dr[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

bool c(int x, int y) {
	return x >= 0 && y >= 0 && x < n && y < m && g[x][y] != '.';
}

void dfs(int x, int y) {
	char t = g[x][y];
	g[x][y] = '.';

	for (int i = 0; i < 4; i++) {
		int X = x + dr[i][0], Y = y + dr[i][1];
		if (!c(X, Y)) continue ;
		if (g[X][Y] == t) dfs(X, Y);
		else v[ans&1^1].pb({X, Y});
	}
}

void solve () {
	cin >> n >> m;
	for (int i = 0; i < n; i++) cin >> g[i];
	v[0].pb({0, 0});
	for (ans = 0; v[ans&1].size(); ans++) {
		for (auto i: v[ans&1]) {
			if (c(i[0], i[1])) dfs(i[0], i[1]);
		}
		v[ans&1].clear();
	}
	cout << ans;
}
signed main() {IOS solve(); return 0;}

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