Submission #1140758

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140758		AbdullahIshfaq	Toy (CEOI24_toy)	C++20	73 / 100	82 ms	1896 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MOD 1000000007
void solve(){
	int w, h, k, l, xh, yh, xv, yv, x, y;
	cin >> w >> h >> k >> l;
    cin >> xh >> yh >> xv >> yv;
    vector<vector<bool>> mtx(w, vector<bool>(h));
	vector<vector<bool>> valhei, valwid, reachable;
	valhei = valwid = reachable = mtx;
	char c;
    for(int i = 0; i < h; i++){
        for(int j = 0; j < w; j++){
            cin >> c;
            mtx[j][i] = (c == 'X');
            if (c == '*') {
                x = j;
                y = i;
            }
        }
    }
    for(int i = 0; i < h - 1; i ++) { // horizontal
        int last = -1;
        for(int j = 0; j < w; j ++) {
            if (mtx[j][i] or mtx[j][i+1]) {
                last = j;
            }
            int start = j - k + 1;
            if (start > last) {
                valhei[start][i] = true;
            }
        }
        last = -k;
        for(int j = 0; j < w; j ++) {
            if (valhei[j][i]) {
                last = j;
            }
            valhei[j][i] = j - k < last;
        }
    }
    for(int i = 0; i < w - 1; i++){ // vertical
        int last = -1;
        for(int j = 0; j < h; j++){
            if (mtx[i][j] or mtx[i+1][j]) {
                last = j;
            }
            int start = j - l + 1;
            if (start > last) {
                valwid[i][start] = true;
            }
        }
        last = -l;
        for(int j = 0; j < h; j++){
            if (valwid[i][j]) {
                last = j;
            }
            valwid[i][j] = j - l < last;
        }
    }
    vector<tuple<int,int>> directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    queue<tuple<int, int>> q;
    q.push({xv, yh});
    reachable[xv][yh] = true;
    while (!q.empty()) {
        auto [xi, yi] = q.front();
        q.pop();
        for (auto [dx, dy] : directions) {
            int tmpx = xi + dx;
            int tmpy = yi + dy;
            bool flg = true;
            if(dx){
                if(tmpx < 0 or tmpx >= w){
					continue;
				}
                flg = !valwid[min(tmpx, xi)][tmpy];
            } 
			else{
                if(tmpy < 0 or tmpy >= h){
					continue;
				}
                flg = !valhei[tmpx][min(tmpy, yi)];
            }
            if(flg or reachable[tmpx][tmpy]){
				continue;
			}
            reachable[tmpx][tmpy] = true;
            q.push({tmpx, tmpy});
        }
    }
	if(max(w, h) > 1000){
		reachable[x][y] = 0;
	}
	if(reachable[x][y]){
		cout << "YES" << '\n';
	}
	else{
    	cout << "NO" << '\n';
	}
}
int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	ll tests = 1;
	// cin >> tests;
	for(ll i = 1; i <= tests; i++){
		solve();
	}
}

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