Submission #1087887

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087887		mychecksedad	Toy (CEOI24_toy)	C++17	100 / 100	188 ms	117904 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define en cout << '\n'
#define vi vector<int>
#define pii pair<int, int>
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
const int N = 1500+100;


int n, m, k, l, xh, yh, xv, yv, pref[N][N], H[N][N], V[N][N], vis[N][N], L[N][N], R[N][N], U[N][N], D[N][N], HOR[N][N], VER[N][N], pref2[N][N], pref3[N][N];
string s[N];
int arr[4][2]={
	{0, 1},
	{1, 0},
	{-1, 0},
	{0, -1}
};
int get(int r1, int r2, int c1, int c2){
	return pref[r2][c2] - pref[r1 - 1][c2] - pref[r2][c1 - 1] + pref[r1 - 1][c1 - 1];
}
int get2(int r1, int r2, int c1, int c2){
	return pref2[r2][c2] - pref2[r1 - 1][c2] - pref2[r2][c1 - 1] + pref2[r1 - 1][c1 - 1];
}
int get3(int r1, int r2, int c1, int c2){
	return pref3[r2][c2] - pref3[r1 - 1][c2] - pref3[r2][c1 - 1] + pref3[r1 - 1][c1 - 1];
}
void solve(){
	cin >> m >> n >> k >> l;	
	cin >> yh >> xh >> yv >> xv;
	++xh, ++yh, ++xv, ++yv;
	for(int i = 1; i <= n; ++i){
		cin >> s[i];
		s[i] = " " + s[i];
	}
	for(int i = 0; i <= n; ++i) for(int j = 0; j <= m; ++j) pref[i][j] = 0;
	for(int i = 0; i <= n; ++i) for(int j = 0; j <= m; ++j) pref2[i][j] = pref3[i][j] = H[i][j] = V[i][j] = vis[i][j] = L[i][j] = R[i][j] = D[i][j] = U[i][j] = HOR[i][j] = VER[i][j] = 0;
	for(int i = 1; i <= n; ++i){
		for(int j = 1; j <= m; ++j){
			pref[i][j] = pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1];
			if(s[i][j] == 'X') ++pref[i][j];
		}
	}
	H[xh][yh] = 1;
	queue<pii> q;
	q.push({xh, yh});
	while(!q.empty()){
		int x = q.front().ff;
		int y = q.front().ss;
		q.pop();
		for(int i = 0; i < 4; ++i){
			int nx = x + arr[i][0];
			int ny = y + arr[i][1];
			if(nx > 0 && ny > 0 && nx <= n && ny + k - 1 <= m && H[nx][ny] == 0){
				if(get(nx, nx, ny, ny + k - 1) == 0){
					H[nx][ny] = 1;
					q.push({nx, ny});
				}
			}
		}
	}
	V[xv][yv] = 1;
	q.push({xv, yv});
	while(!q.empty()){
		int x = q.front().ff;
		int y = q.front().ss;
		q.pop();
		for(int i = 0; i < 4; ++i){
			int nx = x + arr[i][0];
			int ny = y + arr[i][1];
			if(nx > 0 && ny > 0 && nx + l - 1 <= n && ny <= m && V[nx][ny] == 0){
				if(get(nx, nx+l-1, ny, ny) == 0){
					V[nx][ny] = 1;
					q.push({nx, ny});
				}
			}
		}
	}
	for(int i = 1; i <= n; ++i){
		for(int j = 1; j <= m; ++j){
			if(H[i][j] && H[i + 1][j]) VER[i][j] = 1;
			if(V[i][j] && V[i][j + 1]) HOR[i][j] = 1;
		}
	}
	for(int i = 1; i <= n; ++i){
		for(int j = 1; j <= m; ++j){
			pref2[i][j] = pref2[i - 1][j] + pref2[i][j - 1] - pref2[i - 1][j - 1];
			if(VER[i][j]) pref2[i][j]++;
			pref3[i][j] = pref3[i - 1][j] + pref3[i][j - 1] - pref3[i - 1][j - 1];
			if(HOR[i][j]) pref3[i][j]++;
		}
	}

	for(int i = n; i >= 1; --i){
		for(int j = m; j >= 1; --j){
			if(s[i][j] == 'X') continue;
			R[i][j] = get3(max(1, i-l+1), i, j, j);
			L[i][j] = get3(max(1, i-l+1), i, j-1, j-1);
			D[i][j] = get2(i, i, max(1, j-k+1), j);
			U[i][j] = get2(i-1, i-1, max(1, j-k+1), j);
		// 	for(int i1 = i; i1 >= max(1, i - l + 1); --i1)
		// 			if(get(i1, i, j, j) == 0 && V[i1][j]){
		// 				if(V[i1][j + 1]) R[i][j] = 1;
		// 				if(V[i1][j - 1]) L[i][j] = 1;
		// 			}
		// 	for(int i1 = j; i1 >= max(1, j - k + 1); --i1)
		// 			if(get(i, i, i1, j) == 0 && H[i][i1]){
		// 				if(H[i - 1][i1]) U[i][j] = 1;
		// 				if(H[i + 1][i1]) D[i][j] = 1;
		// 			}
		}
	}
	// for(int i = 1; i <= n; ++i){
	// 	for(int j = 1; j <= m; ++j){
	// 		cout << L[i][j];
	// 	}
	// 	en;
	// }
	// assert(H[xh][yv] && V[xh][yv]);
	vis[xh][yv] = 1;
	q.push({xh, yv});
	while(!q.empty()){
		int x = q.front().ff;
		int y = q.front().ss;
		q.pop();
		for(int i = 0; i < 4; ++i){
			int nx = x + arr[i][0];
			int ny = y + arr[i][1];
			if(nx > 0 && ny > 0 && nx <= n && ny <= m && !vis[nx][ny] && s[nx][ny] != 'X'){
				if((nx == x - 1 && U[x][y]) || (nx == x + 1 && D[x][y]) || (ny == y + 1 && R[x][y]) || (ny == y - 1 && L[x][y])){
					vis[nx][ny] = 1;
					q.push({nx, ny});
				}
			}
		}
	}
	for(int i = 1; i <= n; ++i){
		for(int j = 1; j <= m; ++j){
			if(s[i][j] == '*' && vis[i][j]){
				cout << "YES";
				return;
			}
		}
	}
	cout << "NO";
}

int main(){
	cin.tie(0); ios::sync_with_stdio(0);
	solve();
	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