Submission #1173052

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173052		ortsac	Toy (CEOI24_toy)	C++20	100 / 100	519 ms	234288 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);
    }
}

int w, h, wp, hp;
int xh, yh, xv, yv;

pii findLRCol(int row, int col) {
    int po = (upper_bound(inCol[col].begin(), inCol[col].end(), row) - inCol[col].begin());
    int l = -1, r = h;
    if (po < inCol[col].size()) {
        r = inCol[col][po];
    }
    if (po > 0) {
        l = inCol[col][po - 1];
    }
    return {l, r};
}

pii findLRRow(int row, int col) {
    int po = (upper_bound(inRow[row].begin(), inRow[row].end(), col) - inRow[row].begin());
    int l = -1, r = w;
    if (po < inRow[row].size()) {
        r = inRow[row][po];
    }
    if (po > 0) {
        l = inRow[row][po - 1];
    }
    return {l, r};
}

int32_t main() {
    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')) {
                pii lr = {-1, 1e9};
                pii res;
                res = findLRCol(i, j);
                lr.first = max(lr.first, res.first);
                lr.second = min(lr.second, res.second);
                res = findLRCol(i, j + 1);
                lr.first = max(lr.first, res.first);
                lr.second = min(lr.second, res.second);
                int l = lr.first;
                int r = lr.second;
                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')) {
                pii lr = {-1, 1e9};
                pii res;
                res = findLRCol(i, j);
                lr.first = max(lr.first, res.first);
                lr.second = min(lr.second, res.second);
                res = findLRCol(i, j - 1);
                lr.first = max(lr.first, res.first);
                lr.second = min(lr.second, res.second);
                int l = lr.first;
                int r = lr.second;
                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')) {
                pii lr = {-1, 1e9};
                pii res;
                res = findLRRow(i, j);
                lr.first = max(lr.first, res.first);
                lr.second = min(lr.second, res.second);
                res = findLRRow(i + 1, j);
                lr.first = max(lr.first, res.first);
                lr.second = min(lr.second, res.second);
                int l = lr.first;
                int r = lr.second;
                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')) {
                pii lr = {-1, 1e9};
                pii res;
                res = findLRRow(i, j);
                lr.first = max(lr.first, res.first);
                lr.second = min(lr.second, res.second);
                res = findLRRow(i - 1, j);
                lr.first = max(lr.first, res.first);
                lr.second = min(lr.second, res.second);
                int l = lr.first;
                int r = lr.second;
                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: 14 / 14
• Subtask 2: 21 / 21
• Subtask 3: 9 / 9
• Subtask 4: 29 / 29
• Subtask 5: 27 / 27