Submission #362389

#	Time	Username	Problem	Language	Result	Execution time	Memory
362389		__SIGSEGV__	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	752 ms	128860 KiB

tracks

#include <bits/stdc++.h>
#define rep(x,a,b) for (int x = (int) (a); x < (int) (b); x++) 
#define REP(x,a) for (int x = 0; x < (int) (a); x++)
#define per(x,a,b) for (int x = (int) (a); x >= (int) (b); x--)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define eb emplace_back
#define tcT template<class T
#define tcTU template<class T, class U

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const ll INF = (ll) 1e18;
const int X[]={1,0,-1,0}, Y[]={0, -1, 0, 1};
/*BITS*/
int csb(int x) { return __builtin_popcount(x); }
int ctz(int x) { return __builtin_ctz(x); }
bool isSet(int x, int pos) { return (x & (1 << pos)) != 0; }
tcT> bool cmin(T &a, T b) { return a > b ? (a = b, true) : false; }
tcT> bool cmax(T &a, T b) { return a < b ? (a = b, true) : false; }

int main() 
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	cout.precision(10);
	cout << fixed;
	int h, w;
	cin >> h >> w;
	vector<string> grid(h);
	for (int i = 0; i < h; i++)
		cin >> grid[i];
	deque<pii> q;
	vector<vector<int>> dep(h, vector<int>(w, INT_MAX));
	vector<vector<bool>> vis(h, vector<bool>(w, false));
	q.push_front({0, 0});
	dep[0][0] = 1;
	vis[0][0] = true;
	int answer = 0;
	while (!q.empty()) {
		pii at = q.front();
		// cerr << at.first << " " << at.second << '\n';
		q.pop_front();
		for (int dir = 0; dir < 4; dir++) {
			int i = at.first + Y[dir];
			int j = at.second + X[dir];
			if (i >= 0 && i < h && j >= 0 && j < w && !vis[i][j]) {
				if (grid[i][j] == '.') continue;
				if (grid[i][j] == grid[at.first][at.second]) {
					cmin(dep[i][j], dep[at.first][at.second]);
					cmax(answer, dep[i][j]);
					q.push_front({i, j});
					vis[i][j] = true;
				} else {
					cmin(dep[i][j], dep[at.first][at.second] + 1);
					cmax(answer, dep[i][j]);
					q.push_back({i, j});
					vis[i][j] = true;
				}
			}
		}
	}		
	cout << answer << '\n';
	return 0;
}

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