제출 #1364957

#제출 시각아이디문제언어결과실행 시간메모리
1364957lucaskojimaToy (CEOI24_toy)C++20
100 / 100
434 ms202700 KiB
#include <bits/stdc++.h>

using namespace std;

const int K = 1500;

vector<pair<int, int>> adj[K + 1][K + 1];
bool vis[K + 1][K + 1];

int main() {
  ios::sync_with_stdio(0), cin.tie(0);

  int M, N; cin >> M >> N;
  int H, V; cin >> H >> V;
  int a1, a2, a3, a4; cin >> a1 >> a2 >> a3 >> a4;

  vector<string> a(N + 1);
  for (int i = 1; i <= N; i++) {
    cin >> a[i];
    a[i] = '.' + a[i];
  }

  vector<vector<int>> R(N + 1), C(M + 1);
  for (int i = 1; i <= N; i++) {
    R[i].push_back(0);
    for (int j = 1; j <= M; j++)
      if (a[i][j] == 'X')
        R[i].push_back(j);
    R[i].push_back(M + 1);
  }
  for (int j = 1; j <= M; j++) {
    C[j].push_back(0);
    for (int i = 1; i <= N; i++)
      if (a[i][j] == 'X')
        C[j].push_back(i);
    C[j].push_back(N + 1);
  }

  auto ok = [&](int i, int j) -> bool {
    return 1 <= i && i <= N && 1 <= j && j <= M && a[i][j] != 'X';
  };

  for (int i = 1; i < N; i++)
    for (int j = 1; j < M; j++) {
      { // caso linha
        int l = *prev(upper_bound(R[i].begin(), R[i].end(), j));
        int r = *lower_bound(R[i].begin(), R[i].end(), j);
        int l1 = *prev(upper_bound(R[i + 1].begin(), R[i + 1].end(), j));
        int r1 = *lower_bound(R[i + 1].begin(), R[i + 1].end(), j);
        int sz = min(r, r1) - max(l, l1) - 1;
        if (H <= sz && ok(i + 1, j)) {
          adj[i][j].push_back({i + 1, j});
          adj[i + 1][j].push_back({i, j});
        }
      }
      { // caso coluna
        int l = *prev(upper_bound(C[j].begin(), C[j].end(), i));
        int r = *lower_bound(C[j].begin(), C[j].end(), i);
        int l1 = *prev(upper_bound(C[j + 1].begin(), C[j + 1].end(), i));
        int r1 = *lower_bound(C[j + 1].begin(), C[j + 1].end(), i);
        int sz = min(r, r1) - max(l, l1) - 1;
        if (V <= sz && ok(i, j + 1)) {
          adj[i][j].push_back({i, j + 1});
          adj[i][j + 1].push_back({i, j});
        }
      }
    }

  auto dfs = [&](auto dfs, int i, int j) -> void {
    vis[i][j] = true;
    for (auto [a, b] : adj[i][j])
      if (!vis[a][b])
        dfs(dfs, a, b);
  };
  dfs(dfs, a2+1, a3+1);

  for (int i = 1; i <= N; i++)
    for (int j = 1; j <= M; j++)
      if (a[i][j] == '*') {
        cout << (vis[i][j] ? "YES" : "NO") << '\n';
        return 0;
      }
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…