Submission #1037724

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037724		MilosMilutinovic	Toy (CEOI24_toy)	C++14	100 / 100	322 ms	83988 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int w, h, k, l;
  cin >> w >> h >> k >> l;
  int xh, yh, xv, yv;
  cin >> yh >> xh >> yv >> xv;
  vector<string> s(h);
  for (int i = 0; i < h; i++) {
    cin >> s[i];
  }
  int fx, fy;
  for (int i = 0; i < h; i++) {
    for (int j = 0; j < w; j++) {
      if (s[i][j] == '*') {
        fx = i;
        fy = j;
      }
    }
  }
  vector<vector<int>> cnt(h, vector<int>(w));
  for (int i = 0; i < h; i++) {
    for (int j = 0; j < w; j++) {
      cnt[i][j] = (s[i][j] == 'X' ? 1 : 0);
      if (i > 0) {
        cnt[i][j] += cnt[i - 1][j];
      }
      if (j > 0) {
        cnt[i][j] += cnt[i][j - 1];
      }
      if (i > 0 && j > 0) {
        cnt[i][j] -= cnt[i - 1][j - 1];
      }
    }
  }
  auto GetSum = [&](int x1, int y1, int x2, int y2) {
    int s = cnt[x2][y2];
    if (x1 > 0) {
      s -= cnt[x1 - 1][y2];
    }
    if (y1 > 0) {
      s -= cnt[x2][y1 - 1];
    }
    if (x1 > 0 && y1 > 0) {
      s += cnt[x1 - 1][y1 - 1];
    }
    return s;
  };
  vector<vector<bool>> ch(h, vector<bool>(w));
  vector<vector<bool>> cv(h, vector<bool>(w));
  auto Valid = [&](int x, int y) {
    return 0 <= x && x < h && 0 <= y && y < w && s[x][y] != 'X';
  };
  vector<vector<int>> U(h, vector<int>(w));
  vector<vector<int>> D(h, vector<int>(w));
  vector<vector<int>> L(h, vector<int>(w));
  vector<vector<int>> R(h, vector<int>(w));
  for (int x = 0; x < h; x++) {
    for (int y = 0; y < w; y++) {
      if (s[x][y] == 'X') {
        U[x][y] = D[x][y] = L[x][y] = R[x][y] = -1;
        continue;
      }
      {
        U[x][y] = (int) 1e9;
        int low = max(0, x - l + 1), high = min(x, h - l);
        while (low <= high) {
          int mid = (low + high) >> 1;
          if (GetSum(mid, y, x, y) == 0) {
            U[x][y] = mid;
            high = mid - 1;
          } else {
            low = mid + 1;
          }
        }
      }
      {
        D[x][y] = -1;
        int low = U[x][y], high = min(x, h - l);
        while (low <= high) {
          int mid = (low + high) >> 1;
          if (GetSum(mid, y, mid + l - 1, y) == 0) {
            D[x][y] = mid;
            low = mid + 1;
          } else {
            high = mid - 1;
          }
        }
      }
      {
        L[x][y] = (int) 1e9;
        int low = max(0, y - k + 1), high = min(y, w - k);
        while (low <= high) {
          int mid = (low + high) >> 1;
          if (GetSum(x, mid, x, y) == 0) {
            L[x][y] = mid;
            high = mid - 1;
          } else {
            low = mid + 1;
          }
        }
      }
      {
        R[x][y] = -1;
        int low = L[x][y], high = min(y, w - k);
        while (low <= high) {
          int mid = (low + high) >> 1;
          if (GetSum(x, mid, x, mid + k - 1) == 0) {
            R[x][y] = mid;
            low = mid + 1;
          } else {
            high = mid - 1;
          }
        }
      }
      if (U[x][y] > D[x][y] || L[x][y] > R[x][y]) {
        U[x][y] = D[x][y] = L[x][y] = R[x][y] = -1;
        continue;
      } 
      if (!Valid(U[x][y], y) || !Valid(U[x][y] + l - 1, y) || GetSum(U[x][y], y, U[x][y] + l - 1, y) > 0) {
        U[x][y] = D[x][y] = L[x][y] = R[x][y] = -1;
      }
      if (!Valid(x, L[x][y]) || !Valid(x, L[x][y] + k - 1) || GetSum(x, L[x][y], x, L[x][y] + k - 1) > 0) {
        U[x][y] = D[x][y] = L[x][y] = R[x][y] = -1;
      }
    }
  }
  auto Inter = [&](int l1, int r1, int l2, int r2) {
    return max(l1, l2) <= min(r1, r2);
  };
  int sx = xh, sy = yv;
  vector<vector<bool>> f(h, vector<bool>(w));
  f[sx][sy] = true;
  vector<pair<int, int>> que;
  que.emplace_back(sx, sy);
  for (int b = 0; b < (int) que.size(); b++) {
    int x = que[b].first;
    int y = que[b].second;
    for (int d = 0; d < 4; d++) {
      int nx = x + dx[d];
      int ny = y + dy[d];
      if (!Valid(nx, ny)) {
        continue;
      }
      if (d == 0) {
        if (D[x][y] == x - l + 1 || !Inter(L[x][y], R[x][y], L[nx][ny], R[nx][ny])) {
          continue;
        }
      }
      if (d == 1) {
        if (R[x][y] == y - k + 1 || !Inter(U[x][y], D[x][y], U[nx][ny], D[nx][ny])) {
          continue;
        }
      }
      if (d == 2) {
        if (U[x][y] == x || !Inter(L[x][y], R[x][y], L[nx][ny], R[nx][ny])) {
          continue;
        }
      }
      if (d == 3) {
        if (L[x][y] == y || !Inter(U[x][y], D[x][y], U[nx][ny], D[nx][ny])) {
          continue;
        }
      }
      if (Valid(nx, ny) && !f[nx][ny]) {
        f[nx][ny] = true;
        que.emplace_back(nx, ny);
      }
    }
  }
  cout << (f[fx][fy] ? "YES" : "NO") << '\n';
  return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:178:16: warning: 'fx' may be used uninitialized in this function [-Wmaybe-uninitialized]
  178 |   cout << (f[fx][fy] ? "YES" : "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