Submission #1042990

#	Time	Username	Problem	Language	Result	Execution time	Memory
1042990		Tob	Toy (CEOI24_toy)	C++14	100 / 100	132 ms	55744 KiB

Main

#include <bits/stdc++.h>

#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

typedef long long ll;
typedef pair <ll, ll> pii;

const int N = 1507;

int n, m, tmp1, tmp2, stx, sty, enx, eny;
int le[2];
int mat[N][N], bio[N][N];
int cl[N][N][4];

int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};

int main () {
	FIO;
	cin >> m >> n >> le[1] >> le[0] >> tmp1 >> stx >> sty >> tmp2;
	stx++; sty++;
	
	for (int i = 0; i <= n; i++) mat[i][0] = mat[i][m+1] = 1;
	for (int i = 0; i <= m; i++) mat[0][i] = mat[n+1][i] = 1;
	
	for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) {
		char c; cin >> c;
		mat[i][j] = (c == 'X');
		if (c == '*') enx = i, eny = j;
	}
	
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) cl[i][j][0] = (cl[i][j-1][0] + 1)*(mat[i][j] == 0);
		for (int j = m; j; j--) cl[i][j][2] = (cl[i][j+1][2] + 1)*(mat[i][j] == 0);
	}
	for (int i = 1; i <= m; i++) {
		for (int j = 1; j <= n; j++) cl[j][i][1] = (cl[j-1][i][1] + 1)*(mat[j][i] == 0);
		for (int j = n; j; j--) cl[j][i][3] = (cl[j+1][i][3] + 1)*(mat[j][i] == 0);
	}
	
	queue <pii> q;
	q.push({stx, sty});
	bio[stx][sty] = 1;
	while (!q.empty()) {
		pii p = q.front(); q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = p.F + dx[i], ny = p.S + dy[i];
			if (mat[nx][ny] || bio[nx][ny]) continue;
			int a = min(cl[p.F][p.S][i^1], cl[nx][ny][i^1]), b = min(cl[p.F][p.S][i^3], cl[nx][ny][i^3]);
			if (a+b-1 < le[i&1]) continue;
			q.push({nx, ny});
			bio[nx][ny] = 1;
		}
	}
	
	cout << (bio[enx][eny] ? "YES\n" : "NO\n"); 

	return 0;
}

• Subtask 0: 0 / 0
• Subtask 1: 14 / 14
• Subtask 2: 21 / 21
• Subtask 3: 9 / 9
• Subtask 4: 29 / 29
• Subtask 5: 27 / 27