Submission #1262471

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262471		kikitop1gg	Toy (CEOI24_toy)	C++17	100 / 100	93 ms	43116 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vi vector<ll>
#define vvi vector<vector<ll>>
#define vs vector<string>
#define vc vector<char>
#define vb vector<bool>
#define vp vector<pair<ll, ll>>
#define vpp vector<pair<ll, pair<ll, ll>>>
#define pp pair<ll, ll>
#define qi queue<ll>
#define qp queue<pp>
#define pqi priority_queue<ll>
#define pqp priority_queue<pp>
#define mi map<ll, ll>
#define mpi map<pp, ll>
#define mip map<ll, pp>
#define mp map<pp, pp>
#define mb map<ll, bool>
#define si set<ll>
#define sp set<pp>
#define sc set<char>
#define mod 1000000007
#define inf INT_MAX
#define all(x) (x).begin(), (x).end()
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll n, m, hor, vert;
    cin >> m >> n >> hor >> vert;
    ll xh, yh, xv, yv;
    cin >> xh >> yh >> xv >> yv;
    vs g(n);
    for(int i = 0; i < n; i++) {
        cin >> g[i];
    }
    ll sx, sy, ex, ey;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(g[i][j] == '*') {
                g[i][j] = '.';
                ex = i;
                ey = j;
            }
        }
    }
    sx = xv, sy = yh;
    swap(sx, sy);

    vvi walls_row(n);
    vvi walls_col(m);
    for(int i = 0; i < n; i++) {
        walls_row[i].push_back(-1);
        for(int j = 0; j < m; j++) {
            if(g[i][j] == 'X') {
                walls_row[i].push_back(j);
            }
        }
        walls_row[i].push_back(m);
    }
    for(int j = 0; j < m; j++) {
        walls_col[j].push_back(-1);
        for(int i = 0; i < n; i++) {
            if(g[i][j] == 'X') {
                walls_col[j].push_back(i);
            }
        }
        walls_col[j].push_back(n);
    }

    vp dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    vector<vb> canReach(n, vb(m, false));
    canReach[sx][sy] = true;
    qp q;
    q.push({sx, sy});
    while(q.size()) {
        if(canReach[ex][ey]) break;
        auto[x, y] = q.front();
        q.pop();

        ll up, down, left, right;
        auto it = lower_bound(all(walls_row[x]), y);
        right = *it;
        it--;
        left = *it;
        it = lower_bound(all(walls_col[y]), x);
        down = *it;
        it--;
        up = *it;

        for(auto[dirX, dirY] : dirs) {
            ll newX = x + dirX, newY = y + dirY;
            if(newX < 0 || newX >= n || newY < 0 || newY >= m) continue;
            if(g[newX][newY] == 'X' || canReach[newX][newY]) continue;
            bool can = true;

            ll up2, down2, left2, right2;
            auto it = lower_bound(all(walls_row[newX]), newY);
            right2 = *it;
            it--;
            left2 = *it;
            it = lower_bound(all(walls_col[newY]), newX);
            down2 = *it;
            it--;
            up2 = *it;

            ll l = max(left, left2);
            ll r = min(right, right2);
            if(r - l - 1 < hor) can = false;

            l = max(up, up2);
            r = min(down, down2);
            if(r - l - 1 < vert) can = false;

            if(!can) continue;
            canReach[newX][newY] = true;
            q.push({newX, newY});
        }
    }

    if(canReach[ex][ey]) cout << "YES\n";
    else cout << "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