Submission #1219821

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219821		j_vdd16	Toy (CEOI24_toy)	C++20	100 / 100	507 ms	426480 KiB

Main

#include <algorithm>
#include <bitset>
#include <cstdint>
#include <cstring>
#include <iostream>
#include <limits.h>
#include <math.h>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <chrono>

#define loop(X, N) for(int X = 0; X < (N); X++)
#define all(V) V.begin(), V.end()
#define rall(V) V.rbegin(), V.rend()

using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;

vvb vis;
vector<string> grid;
vvi l, r, t, b;

int m, n, vert, hor;

bool success = false;
void dfs(int i, int j) {
    if (vis[i][j] || r[i][j] + l[i][j] + 1 < hor || b[i][j] + t[i][j] + 1 < vert)
        return;

    vis[i][j] = true;
    if (grid[i][j] == '*')
        success = true;

    if (i > 0 && min(r[i - 1][j] + l[i][j], r[i][j] + l[i - 1][j]) + 1 >= hor)
        dfs(i - 1, j);
    if (j > 0 && min(b[i][j - 1] + t[i][j], b[i][j] + t[i][j - 1]) + 1 >= vert)
        dfs(i, j - 1);
    if (i < n - 1 && min(r[i + 1][j] + l[i][j], r[i][j] + l[i + 1][j]) + 1 >= hor)
        dfs(i + 1, j);
    if (j < m - 1 && min(b[i][j + 1] + t[i][j], b[i][j] + t[i][j + 1]) + 1 >= vert)
        dfs(i, j + 1);
}

int main() {
    cin >> m >> n >> hor >> vert;

    vis = vvb(n, vb(m, false));
    
    int xh, yh, xv, yv;
    cin >> xh >> yh >> xv >> yv;

    grid = vector<string>(n);
    loop(i, n)
        cin >> grid[i];

    l = vvi(n, vi(m, 0));
    t = vvi(n, vi(m, 0));
    loop(i, n) {
        loop(j, m) {
            if (grid[i][j] == 'X') {
                l[i][j] = -1;
                t[i][j] = -1;
            }
            else {
                if (j > 0)
                    l[i][j] = l[i][j - 1] + 1;
                if (i > 0)
                    t[i][j] = t[i - 1][j] + 1;
            }
        }
    }

    r = vvi(n, vi(m, 0));
    b = vvi(n, vi(m, 0));
    for (int i = n - 1; i >= 0; i--) {
        for (int j = m - 1; j >= 0; j--) {
            if (grid[i][j] == 'X') {
                r[i][j] = -1;
                b[i][j] = -1;
            }
            else {
                if (j < m - 1)
                    r[i][j] = r[i][j + 1] + 1;
                if (i < n - 1)
                    b[i][j] = b[i + 1][j] + 1;
            }
        }
    }

    dfs(yh, xv);

    cout << (success ? "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