Submission #1036520

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036520		model_code	Toy (CEOI24_toy)	C++17	100 / 100	236 ms	5572 KiB

Main

// Author: Ondra Sladký
// Alternative optimal solution which is based in the ideas in the (broken) solutions
// coloring edges and vertices.
// It colors edges through which individual rectangles can move. It also colors edges inside
// the rectangles for each position of the rectangle (which is why it works) which is for simplicity
// done using edge coloring of rectangles of size k-1 and l-1.
// It runs in O(wh)
// It should solve every subtask.

#include <bits/stdc++.h>
using namespace std;
#define f(i, a, b) for (int i = (a); i < (b); i++)

#define v vector

int w, h, k, l;
int xhI, yhI, xvI, yvI;
int xt, yt;
v<v<bool>> grid;

v<v<bool>> validH;
v<v<bool>> validV;

v<v<bool>> statesH;
v<v<v<bool>>> stateHedges;
v<v<bool>> statesV;
v<v<v<bool>>> stateVedges;
v<v<bool>> states;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> w >> h >> k >> l;
    cin >> xhI >> yhI >> xvI >> yvI;
    grid = v<v<bool>>(w, v<bool>(h));
    f(i, 0, h) {
        string s;
        cin >> s;
        f(j, 0, w) {
            char x = s[j];
            grid[j][i] = x == 'X';
            if (x == '*') {
                xt = j;
                yt = i;
            }
        }
    }

    // Precompute valid positions for horizontal and vertical blocks.
    validH = v<v<bool>>(w, v<bool>(h, false));
    validV = v<v<bool>>(w, v<bool>(h, false));

    f(i,0,h) {
        int last = -1;
        f(j,0,w) {
            if (grid[j][i]) {
                last = j;
            }
            int start = j - k + 1;
            if (start > last) {
                validH[start][i] = true;
            }
        }
    }

    f(i,0,w) {
        int last = -1;
        f(j,0,h) {
            if (grid[i][j]) {
                last = j;
            }
            int start = j - l + 1;
            if (start > last) {
                validV[i][start] = true;
            }
        }
    }


    auto directions = v<tuple<int, int>> {
        {1, 0},
        {-1, 0},
        {0, 1},
        {0, -1},
    };
    queue<tuple<int, int>> q;
    q.push({xhI, yhI});
    statesH = v<v<bool>>(w, v<bool>(h, false));
    stateHedges = v<v<v<bool>>>(4, v<v<bool>>(w, v<bool>(h, false)));
    statesH[xhI][yhI] = true;
    while (!q.empty()) {
        auto [xh, yh] = q.front();
        q.pop();
        f(index, 0, 4) {
            auto [dx, dy] = directions[index];
            int nxh = xh + dx;
            int nyh = yh + dy;

            // Fast check for obstacles

            bool blocked = false;
            if (nxh < 0 || nxh >= w || nyh < 0 || nyh >= h) blocked = true;
            if (blocked) continue;
            if (!validH[nxh][nyh]) blocked = true;
            if (blocked) continue;

            stateHedges[index][xh][yh] = true;

            if (statesH[nxh][nyh]) continue;
            statesH[nxh][nyh] = true;
            q.push({nxh, nyh});
        }
    }
    // Edge coloring.
    f(d,0,4) {
        f(i,0,h) {
            int last = -k;
            f(j,0,w) {
                if (stateHedges[d][j][i]) {
                    last = j;
                }
                stateHedges[d][j][i] = j - k < last;
            }
        }
    }
    // Vertex coloring with k-1.
    f(i,0,h) {
        int last = -k;
        f(j,0,w) {
            if (statesH[j][i]) {
                last = j;
            }
            statesH[j][i] = j - k + 1 < last;
        }
    }

    q.push({xvI, yvI});
    statesV = v<v<bool>>(w, v<bool>(h, false));
    stateVedges = v<v<v<bool>>>(4, v<v<bool>>(w, v<bool>(h, false)));
    statesV[xvI][yvI] = true;
    while (!q.empty()) {
        auto [xv, yv] = q.front();
        q.pop();
        f(index, 0, 4) {
            auto [dx, dy] = directions[index];
            int nxv = xv + dx;
            int nyv = yv + dy;

            // Fast check for obstacles

            bool blocked = false;
            if (nxv < 0 || nxv >= w || nyv < 0 || nyv >= h) blocked = true;
            if (blocked) continue;
            if (!validV[nxv][nyv]) blocked = true;
            if (blocked) continue;

            stateVedges[index][xv][yv] = true;

            if (statesV[nxv][nyv]) continue;
            statesV[nxv][nyv] = true;
            q.push({nxv, nyv});
        }
    }
    // Edge coloring.
    f(d,0,4){
        f(i,0,w) {
            int last = -l;
            f(j,0,h) {
                if (stateVedges[d][i][j]) {
                    last = j;
                }
                stateVedges[d][i][j] = j - l < last;
            }
        }
    }
    // Vertex coloring with l-1.
    f(i,0,w) {
        int last = -l;
        f(j,0,h) {
            if (statesV[i][j]) {
                last = j;
            }
            statesV[i][j] = j - l + 1 < last;
        }
    }

    // Find a path from (xvI, yhI) to (xt, yt) that is edge-colored by both rectangles.

    q.push({xvI, yhI});
    states = v<v<bool>>(w, v<bool>(h, false));
    states[xvI][yhI] = true;
    while(!q.empty()) {
        auto [xv, yv] = q.front();
        q.pop();
        f(index, 0, 4) {
            auto [dx, dy] = directions[index];
            int nxv = xv + dx;
            int nyv = yv + dy;
            if (nxv < 0 || nxv >= w || nyv < 0 || nyv >= h) continue;
            bool Hgood = stateHedges[index][xv][yv];
            if (dx != 0) {
                if (statesH[min(xv, nxv)][yv]) Hgood = true;
            }
            bool Vgood = stateVedges[index][xv][yv];
            if (dy != 0) {
                if (statesV[xv][min(yv, nyv)]) Vgood = true;
            }
            if (!Hgood || !Vgood) continue;
            if (states[nxv][nyv]) continue;
            states[nxv][nyv] = true;
            q.push({nxv, nyv});
        }
    }


    bool reached = states[xt][yt];

    cout << (reached ? "YES" : "NO") << endl;
}

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