Submission #1249188

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249188		domi	Toy (CEOI24_toy)	C++20	100 / 100	172 ms	91084 KiB

Main

#include <bits/stdc++.h>

#define int long long
#define fi first
#define se second

#define sz(a) (int)((a).size())
#define all(a) (a).begin(), (a).end()

#define lsb(x) (x & (-x))
#define vi vector<int>
#define YES { cout << "YES" << endl; return; }
#define NO { cout << "NO" << endl; return; }

using ll = long long;
using pii = std::pair<int, int>;

const int dlin[] = {-1, 1, 0, 0};
const int dcol[] = {0, 0, -1, 1};
const int NMAX = 15e2;

using namespace std;

char mat[NMAX + 5][NMAX + 5];
int viz[NMAX + 5][NMAX + 5], n, m, K, L, xh, yh, xv, yv, xd, yd;
int l[NMAX + 5][NMAX + 5], r[NMAX + 5][NMAX + 5], u[NMAX + 5][NMAX + 5], d[NMAX + 5][NMAX + 5];

void prec() {
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j)
            l[i][j] = (mat[i][j] == 'X' ? j : l[i][j - 1]);

        r[i][m + 1] = m + 1;
        for (int j = m; j >= 1; --j)
            r[i][j] = (mat[i][j] == 'X' ? j : r[i][j + 1]);
    }

    for (int j = 1; j <= m; ++j) {
        for (int i = 1; i <= n; ++i)
            u[i][j] = (mat[i][j] == 'X' ? i : u[i - 1][j]);

        d[n + 1][j] = n + 1;
        for (int i = n; i >= 1; --i)
            d[i][j] = (mat[i][j] == 'X' ? i : d[i + 1][j]);
    }

}

bool inbound(int r, int c) {
    return (r >= 1 && r <= n && c >= 1 && c <= m);
}

bool tranzitie(int a, int b, int x, int y) {
    if (b == y)
        return min(r[a][b], r[x][y]) - max(l[a][b], l[x][y]) - 1 >= K;
    return min(d[a][b], d[x][y]) - max(u[a][b], u[x][y]) - 1 >= L;
}

void bfs() {
    queue<pii>Q;
    viz[yh][xv] = true;
    Q.push({yh, xv});

    while (!Q.empty()) {
        auto [x, y] = Q.front();
        Q.pop();

        for (int dir = 0; dir < 4 ; ++dir) {
            int lin = x + dlin[dir];
            int col = y + dcol[dir];

            if (inbound(lin, col) && mat[lin][col] != 'X' && !viz[lin][col] && tranzitie(x, y, lin, col)) {
                viz[lin][col] = true;
                Q.push({lin, col});
            }
        }
    }
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> m >> n >> K >> L >> xh >> yh >> xv >> yv;
    ++xh, ++yh;
    ++xv, ++yv;

    for (int i = 1; i <= n; ++i) {

        for (int j = 1; j <= m; ++j) {
            cin >> mat[i][j];
            if (mat[i][j] == '*')
                tie(xd, yd) = make_pair(i, j);
        }
    }

    prec();
    bfs();
    cout << (viz[xd][yd] ? "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