Submission #1212413

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212413		yanb	Toy (CEOI24_toy)	C++20	100 / 100	431 ms	340484 KiB

Main

#include <bits/stdc++.h>
 
#define int long long
 
using namespace std;

void dfs(int v, vector<vector<int>> &g, vector<bool> &uu) {
    if (uu[v]) return;
    uu[v] = 1;
    for (int u : g[v]) dfs(u, g, uu);
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    
    int w, h, k, l;
    cin >> w >> h >> k >> l;
    int xh, yh, xv, yv;
    cin >> xh >> yh >> xv >> yv;

    vector<string> a(h + 2);
    for (int j = 0; j < w + 2; j++) {
        a[0] += 'X';
        a[h + 1] += 'X';
    }
    for (int i = 1; i <= h; i++) {
        string t;
        cin >> t;
        a[i] = 'X' + t + 'X';
    }

    w += 2, h += 2;
    int sx = xv + 1, sy = yh + 1;
    int ex, ey;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            if (a[i][j] == '*') {
                ex = j, ey = i;
            }
        }
    }

    vector<vector<int>> Bl(h, vector<int>(w, -1)), Br(h, vector<int>(w, -1)), Bu(h, vector<int>(w, -1)),
                        Bd(h, vector<int>(w, -1));
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            if (a[i][j] == 'X') {
                Bl[i][j] = Br[i][j] = j;
                Bu[i][j] = Bd[i][j] = i;
            }
        }
    }
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w - 1; j++) {
            if (Bl[i][j + 1] == -1) Bl[i][j + 1] = Bl[i][j];
        }
    }
    for (int i = 0; i < h; i++) {
        for (int j = w - 1; j > 0; j--) {
            if (Br[i][j - 1] == -1) Br[i][j - 1] = Br[i][j];
        }
    }
    for (int i = 0; i < h - 1; i++) {
        for (int j = 0; j < w; j++) {
            if (Bu[i + 1][j] == -1) Bu[i + 1][j] = Bu[i][j];
        }
    }
    for (int i = h - 1; i > 0; i--) {
        for (int j = 0; j < w; j++) {
            if (Bd[i - 1][j] == -1) Bd[i - 1][j] = Bd[i][j];
        }
    }

    vector<vector<int>> g(w * h); // y * w + x
    for (int y = 0; y < h; y++) {
        for (int x = 0; x < w - 1; x++) {
            if (a[y][x] != 'X' && a[y][x + 1] != 'X') {
                int U = max(Bu[y][x], Bu[y][x + 1]);
                int D = min(Bd[y][x], Bd[y][x + 1]);
                if (D - U - 1 >= l) {
                    g[y * w + x].push_back(y * w + (x + 1));
                    g[y * w + (x + 1)].push_back(y * w + x);
                }
            }
        }
    }
    for (int y = 0; y < h - 1; y++) {
        for (int x = 0; x < w; x++) {
            if (a[y][x] != 'X' && a[y + 1][x] != 'X') {
                int L = max(Bl[y][x], Bl[y + 1][x]);
                int R = min(Br[y][x], Br[y + 1][x]);
                if (R - L - 1 >= k) {
                    g[y * w + x].push_back((y + 1) * w + x);
                    g[(y + 1) * w + x].push_back(y * w + x);
                }
            }
        }
    }

    vector<bool> uu(w * h);
    dfs(sy * w + sx, g, uu);
    cout << (uu[ey * w + ex] ? "YES\n" : "NO\n");
}

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