Submission #499005

#	Time	Username	Problem	Language	Result	Execution time	Memory
499005		vbee	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	761 ms	238576 KiB

tracks

#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define ii pair<int,int>
#define vii vector<ii>
#define vi vector<int>
#define fi first
#define se second
#define TASK ""
#define ll long long
#define pll pair<ll, ll>
#define vll vector<ll>
#define vpll vector<pll>
#define pb push_back
#define MASK(i) (1 << (i))
#define BIT(x, i) ((x >> (i)) & 1)
 
using namespace std;

const int oo = 1e9 + 7;
const ll loo = (ll)1e18 + 7;
const int N = 4e3 + 7; 
ll n, m, dist[N][N];
char a[N][N];
bool visited[N][N];
const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};
bool check(ll i, ll j){
	if (i < 1 || j < 1 || i > n || j > m || a[i][j] == '.' || visited[i][j]) return false;
	return true;
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	//freopen(TASK".in", "r", stdin);
	//freopen(TASK".out", "w", stdout);
	cin >> n >> m;
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= m; j++){
			cin >> a[i][j];
		}
	}
	deque<pll> kew;
	kew.push_back({1, 1});
	visited[1][1] = true;
	ll res = 0;
	while (!kew.empty()){
		auto k = kew.front();
		kew.pop_front();
		res = max(res, dist[k.fi][k.se]);
		for (int i = 0; i < 4; i++){
			ll newx = k.fi + dx[i];
			ll newy = k.se + dy[i];
			if (check(newx, newy)){
				visited[newx][newy] = true;
				dist[newx][newy] = dist[k.fi][k.se];
				if (a[k.fi][k.se] == a[newx][newy]){
					kew.push_front({newx, newy});
				}
				else {
					dist[newx][newy]++;
					kew.push_back({newx, newy});
				}
			}
		}
	}
	cout << res + 1;
	return 0;
}

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