Submission #1283169

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283169		dashka	Toy (CEOI24_toy)	C++20	100 / 100	157 ms	40588 KiB

Main

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#include <cmath>
// #pragma GCC optimize("Ofast")
// #pragma GCC target("avx,avx2,fma")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,sse4a,avx,avx2,popcnt,tune=native")
typedef long long ll;
using namespace std;

int inter(int lx, int rx, int ly, int ry) {
    return max(0, min(rx, ry) - max(lx, ly) - 1);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int w, h, k, l, xh, yh, xv, yv;
    cin >> w >> h >> k >> l >> yh >> xh >> yv >> xv;
    ++xh; ++yh; ++xv; ++yv;

    vector<string> s(h + 2);
    for (int i = 1; i <= h; ++i) {
        string row;
        cin >> row;
        s[i] = "#" + row;
    }
    int xf = -1, yf = -1;
    for (int i = 1; i <= h; ++i) {
        for (int j = 1; j <= w; ++j) {
            if (s[i][j] == '*') {
                xf = i; yf = j;
            }
        }
    }

    vector<vector<int>> lft(h + 2, vector<int>(w + 2, 0));
    vector<vector<int>> rgh(h + 2, vector<int>(w + 2, w + 1));
    vector<vector<int>> up(h + 2, vector<int>(w + 2, 0));
    vector<vector<int>> down(h + 2, vector<int>(w + 2, h + 1));
    vector<vector<char>> vis(h + 2, vector<char>(w + 2, 0));
    for (int i = 1; i <= h; ++i) {
        for (int j = 1; j <= w; ++j) {
            lft[i][j] = lft[i][j - 1];
            up[i][j]  = up[i - 1][j];
            if (s[i][j] == 'X') {
                lft[i][j] = j;
                up[i][j]  = i;
            }
        }
    }

    for (int i = 1; i <= h + 1; ++i) {
        for (int j = 1; j <= w + 1; ++j) {
            rgh[i][j]  = w + 1;
            down[i][j] = h + 1;
        }
    }

    for (int i = h; i >= 1; --i) {
        for (int j = w; j >= 1; --j) {
            rgh[i][j]  = rgh[i][j + 1];
            down[i][j] = down[i + 1][j];
            if (s[i][j] == 'X') {
                rgh[i][j]  = j;
                down[i][j] = i;
            }
        }
    }

    queue<pair<int,int>> q;
    q.push({xh, yv});
    while (!q.empty()) {
        auto [x, y] = q.front(); q.pop();
        if (vis[x][y]) continue;
        vis[x][y] = 1;
        if (y + 1 <= w && inter(up[x][y], down[x][y], up[x][y + 1], down[x][y + 1]) >= l) {
            q.push({x, y + 1});
        }
        if (y - 1 >= 1 && inter(up[x][y], down[x][y], up[x][y - 1], down[x][y - 1]) >= l) {
            q.push({x, y - 1});
        }
        if (x + 1 <= h && inter(lft[x][y], rgh[x][y], lft[x + 1][y], rgh[x + 1][y]) >= k) {
            q.push({x + 1, y});
        }
        if (x - 1 >= 1 && inter(lft[x][y], rgh[x][y], lft[x - 1][y], rgh[x - 1][y]) >= k) {
            q.push({x - 1, y});
        }
    }

    cout << (vis[xf][yf] ? "YES" : "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