Submission #1036514

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036514		model_code	Toy (CEOI24_toy)	C++17	100 / 100	516 ms	129812 KiB

Main

// Author: Dan Skýpala
// O(wh) correct solution
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>

using namespace std;

int w, h, k, l;
int xh0, yh0, xv0, yv0;
vector<vector<bool>> field;
vector<vector<int>> up_space, down_space, left_space, right_space;
int tx=-1, ty=-1;

struct raw_pos {
    int x, y;
    bool const operator==(const raw_pos& p) const {
        return (x == p.x && y == p.y);
    }
};

struct pos : raw_pos {
    pos(int x1, int y1) {
        x = x1;
        y = y1;
    }
    bool isValid(const pos& new_p) const {
        return (
            min(left_space[y][x], left_space[new_p.y][new_p.x]) + min(right_space[y][x], right_space[new_p.y][new_p.x]) - (x == new_p.x) >= k
            &&
            min(up_space[y][x], up_space[new_p.y][new_p.x]) + min(down_space[y][x], down_space[new_p.y][new_p.x]) - (y == new_p.y) >= l
        );
    }
};

struct Hash {
    size_t operator() (const pos& p) const {
        return p.x + (p.y << 11);
    }
};

queue<pos> q;
unordered_set<pos, Hash> vis;
void add(const pos& p, const pos& new_p) {
    if (p.isValid(new_p) && vis.count(new_p) == 0) {
        q.push(new_p);
        vis.insert(new_p);
    }
}

bool search(pos p0) {
    add(p0, p0);

    while (q.size()) {
        pos p = q.front(); q.pop();

#ifdef DBG
        vector<vector<char>> f(h, vector<char>(w, '.'));

        for (int i=0; i<w+5; i++)
            cout << "-";
        cout << endl;
        
        f[p.y][p.x] = '+';
        f[ty][tx] = '*';
        for (int i=0; i<h; i++) {
            for (int j=0; j<w; j++) {
                if (!field[i][j])
                    cout << "#";
                else
                    cout << f[i][j];
            }
            cout << endl;
        }
#endif

        if (p.x == tx && p.y == ty) {
            return true;
        }
        add(p, {p.x-1, p.y});
        add(p, {p.x+1, p.y});
        add(p, {p.x, p.y-1});
        add(p, {p.x, p.y+1});
    }
    return false;
}

int calc_space(vector<vector<int>>& s, int x, int y, int dx, int dy) {
    if (s[y][x] == -1) {
        if (field[y][x]) {
            s[y][x] = calc_space(s, x+dx, y+dy, dx, dy) + 1;
        } else {
            s[y][x] = 0;
        }
    }
    return s[y][x];
}

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

    cin >> w >> h >> k >> l;
    w += 2; h += 2;
    field.resize(h, vector<bool>(w, false));
    left_space.resize(h, vector<int>(w, -1));
    right_space.resize(h, vector<int>(w, -1));
    down_space.resize(h, vector<int>(w, -1));
    up_space.resize(h, vector<int>(w, -1));

    cin >> xh0 >> yh0 >> xv0 >> yv0;
    xh0++; yh0++; xv0++; yv0++;

    for (int y=1; y<h-1; y++) {
        string row;
        cin >> row;
        for (int x=1; x<w-1; x++) {
            if (row[x-1] == '*') {
                ty = y; tx = x;
            }
            field[y][x] = (row[x-1] != 'X');
        }
    }

    for (int y=0; y<h; y++) {
        for (int x=0; x<w; x++) {
            calc_space(left_space, x, y, -1, 0);
            calc_space(right_space, x, y, 1, 0);
            calc_space(up_space, x, y, 0, -1);
            calc_space(down_space, x, y, 0, 1);
        }
    }

    if (search({xv0, yh0})) {
        cout << "YES" << endl;
    } else {
        cout << "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