Submission #1173043

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173043		ortsac	Toy (CEOI24_toy)	C++20	0 / 100	42 ms	61512 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define pii pair<int, int>

const int MAXN = 1505;

vector<pii> adj[MAXN][MAXN];
char mat[MAXN][MAXN];
vector<int> inCol[MAXN];
vector<int> inRow[MAXN];
bool vis[MAXN][MAXN];

void dfs(int x, int y) {
    if (vis[x][y]) return;
    vis[x][y] = 1;
    for (auto u : adj[x][y]) {
        dfs(u.first, u.second);
    }
}

int32_t main() {
    int w, h, wp, hp;
    int xh, yh, xv, yv;
    cin >> w >> h >> wp >> hp;
    cin >> xh >> yh >> xv >> yv;
    int x = yh, y = xv;
    int tx, ty;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            cin >> mat[i][j];
            if (mat[i][j] == 'X') {
                inRow[i].push_back(j);
                inCol[j].push_back(i);
            }
            if (mat[i][j] == '*') {
                tx = i;
                ty = j;
            }
        }
    }
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            // from point {i, j}
            // {i, j + 1}
            if (((j + 1) < w) && (mat[i][j + 1] != 'X')) {
                int po = (upper_bound(inCol[j + 1].begin(), inCol[j + 1].end(), i) - inCol[j + 1].begin());
                int l = -1, r = h;
                if (po < inCol[j + 1].size()) {
                    r = inCol[j + 1][po];
                }
                if (po > 0) {
                    l = inCol[j + 1][po - 1];
                }
                if ((r - l - 1) >= hp) adj[i][j].push_back({i, j + 1});
            }
            // {i, j - 1}
            if (((j - 1) >= 0) && (mat[i][j - 1] != 'X')) {
                int po = (upper_bound(inCol[j - 1].begin(), inCol[j - 1].end(), i) - inCol[j - 1].begin());
                int l = -1, r = h;
                if (po < inCol[j - 1].size()) {
                    r = inCol[j - 1][po];
                }
                if (po > 0) {
                    l = inCol[j - 1][po - 1];
                }
                if ((r - l - 1) >= hp) adj[i][j].push_back({i, j - 1});
            }
            // {i + 1, j}
            if (((i + 1) < h) && (mat[i + 1][j] != 'X')) {
                int po = (upper_bound(inRow[i + 1].begin(), inRow[i + 1].end(), j) - inRow[i + 1].begin());
                int l = -1, r = w;
                if (po < inRow[i + 1].size()) {
                    r = inRow[i + 1][po];
                }
                if (po > 0) {
                    l = inRow[i + 1][po - 1];
                }
                if ((r - l - 1) >= wp) adj[i][j].push_back({i + 1, j});
            }
            // {i - 1, j}
            if (((i - 1) >= 0) && (mat[i - 1][j] != 'X')) {
                int po = (upper_bound(inRow[i - 1].begin(), inRow[i - 1].end(), j) - inRow[i - 1].begin());
                int l = -1, r = w;
                if (po < inRow[i - 1].size()) {
                    r = inRow[i - 1][po];
                }
                if (po > 0) {
                    l = inRow[i - 1][po - 1];
                }
                if ((r - l - 1) >= wp) adj[i][j].push_back({i - 1, j});
            }
        }
    }
    dfs(x, y);
    if (vis[tx][ty]) {
        cout << "YES\n";
    } else {
        cout << "NO\n";
    }
}

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