Submission #722296

#	Time	Username	Problem	Language	Result	Execution time	Memory
722296		NothingXD	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	1145 ms	92344 KiB

tracks

/*

   Wei Wai Wei Wai
   Zumigat nan damu dimi kwayt rayt

*/

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

typedef long long ll;
typedef double ld;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef complex<ld> point;
/*typedef __uint128_t L;
  struct FastMod {
  ull b, m;
  FastMod(ull b) : b(b), m(ull((L(1) << 64) / b)) {}
  ull reduce(ull a) {
  ull q = (ull)((L(m) * a) >> 64);
  ull r = a - q * b; // can be proven that 0 <= r < 2*b
  return r >= b ? r - b : r;
  }
  };
  FastMod FM(2);
  */
void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
	cerr << " " << H;
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "):", debug_out(__VA_ARGS__)
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)
#define F first
#define S second

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 4e3 + 10;

int n, m, a[maxn][maxn];
bool vis[maxn][maxn];

int xc[4] = {1, -1, 0, 0};
int yc[4] = {0, 0, 1, -1};

inline bool isvalid(int x, int y){
	return (x && x <= n && y && y <= m && !vis[x][y] && a[x][y] != 2);
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);

	cin >> n >> m;

	char mark;

	for (int i = 1; i <= n; i++){
		string s; cin >> s;
		if (i == 1) mark = s[0];
		for (int j = 1; j <= m; j++){
			if (s[j-1] == '.') a[i][j] = 2;
			else if (s[j-1] != mark) a[i][j] = 1;
		}
	}
	queue<pii> q[2];
	int ans = 0;
	q[0].push({1, 1});
	vis[1][1] = true;
	for (int tmp = 0;; tmp++){
		int idx = tmp&1;
		if (q[idx].empty()) break;
		ans++;
		while(!q[idx].empty()){
			int x = q[idx].front().F, y = q[idx].front().S;
			q[idx].pop();
			for (int i = 0; i < 4; i++){
				int ux = x + xc[i];
				int uy = y + yc[i];
				if (isvalid(ux, uy)){
					q[a[ux][uy]].push({ux, uy});
					vis[ux][uy] = true;
				}
			}
		}
	}

	cout << ans << '\n';

	return 0;
}

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