Submission #1041025

#	Time	Username	Problem	Language	Result	Execution time	Memory
1041025		Lucpp	Toy (CEOI24_toy)	C++17	100 / 100	74 ms	40888 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)size(x)

int main(){
	cin.tie(0)->sync_with_stdio(false);
  int w, h, lenW, lenH, sx, sy, trash;
  cin >> w >> h >> lenW >> lenH;
  cin >> trash >> sy >> sx >> trash;
  vector<string> grid(h);
  for(int i = 0; i < h; i++) cin >> grid[i];
  vector<vector<int>> nup(h, vector<int>(w)), ndown(h, vector<int>(w)), nleft(h, vector<int>(w)), nright(h, vector<int>(w));
  for(int i = 0; i < h; i++){
    for(int j = 0; j < w; j++){
      if(grid[i][j] == 'X') nup[i][j] = i, nleft[i][j] = j;
      else{
        nup[i][j] = i > 0 ? nup[i-1][j] : -1;
        nleft[i][j] = j > 0 ? nleft[i][j-1] : -1;
      }
    }
  }
  for(int i = h-1; i >= 0; i--){
    for(int j = w-1; j >= 0; j--){
      if(grid[i][j] == 'X') ndown[i][j] = i, nright[i][j] = j;
      else{
        ndown[i][j] = i < h-1 ? ndown[i+1][j] : h;
        nright[i][j] = j < w-1 ? nright[i][j+1] : w;
      }
    }
  }
  queue<pair<int, int>> q;
  q.emplace(sy, sx);
  vector<vector<bool>> vis(h, vector<bool>(w));
  vis[sy][sx] = true;
  bool ans = false;
  while(!q.empty()){
    auto [i, j] = q.front(); q.pop();
    if(grid[i][j] == '*') ans = true;
    auto checkHor = [&](int a, int b){
      int toR = min(nright[a][j], nright[b][j]);
      int toL = max(nleft[a][j], nleft[b][j]);
      return toR - toL - 1 >= lenW;
    };
    auto checkVer = [&](int a, int b){
      int toD = min(ndown[i][a], ndown[i][b]);
      int toU = max(nup[i][a], nup[i][b]);
      return toD - toU - 1 >= lenH;
    };
    if(i > 0 && !vis[i-1][j] && grid[i-1][j] != 'X'){
      if(checkHor(i, i-1)){
        q.emplace(i-1, j);
        vis[i-1][j] = true;
      }
    }
    if(i < h-1 && !vis[i+1][j] && grid[i+1][j] != 'X'){
      if(checkHor(i, i+1)){
        q.emplace(i+1, j);
        vis[i+1][j] = true;
      }
    }
    if(j > 0 && !vis[i][j-1] && grid[i][j-1] != 'X'){
      if(checkVer(j, j-1)){
        q.emplace(i, j-1);
        vis[i][j-1] = true;
      }
    }
    if(j < w-1 && !vis[i][j+1] && grid[i][j+1] != 'X'){
      if(checkVer(j, j+1)){
        q.emplace(i, j+1);
        vis[i][j+1] = true;
      }
    }
  }
  if(ans) cout << "YES\n";
  else cout << "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