Submission #1262471

#TimeUsernameProblemLanguageResultExecution timeMemory
1262471kikitop1ggToy (CEOI24_toy)C++17
100 / 100
93 ms43116 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define vi vector<ll> #define vvi vector<vector<ll>> #define vs vector<string> #define vc vector<char> #define vb vector<bool> #define vp vector<pair<ll, ll>> #define vpp vector<pair<ll, pair<ll, ll>>> #define pp pair<ll, ll> #define qi queue<ll> #define qp queue<pp> #define pqi priority_queue<ll> #define pqp priority_queue<pp> #define mi map<ll, ll> #define mpi map<pp, ll> #define mip map<ll, pp> #define mp map<pp, pp> #define mb map<ll, bool> #define si set<ll> #define sp set<pp> #define sc set<char> #define mod 1000000007 #define inf INT_MAX #define all(x) (x).begin(), (x).end() int main() { ios_base::sync_with_stdio(0); cin.tie(0); ll n, m, hor, vert; cin >> m >> n >> hor >> vert; ll xh, yh, xv, yv; cin >> xh >> yh >> xv >> yv; vs g(n); for(int i = 0; i < n; i++) { cin >> g[i]; } ll sx, sy, ex, ey; for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { if(g[i][j] == '*') { g[i][j] = '.'; ex = i; ey = j; } } } sx = xv, sy = yh; swap(sx, sy); vvi walls_row(n); vvi walls_col(m); for(int i = 0; i < n; i++) { walls_row[i].push_back(-1); for(int j = 0; j < m; j++) { if(g[i][j] == 'X') { walls_row[i].push_back(j); } } walls_row[i].push_back(m); } for(int j = 0; j < m; j++) { walls_col[j].push_back(-1); for(int i = 0; i < n; i++) { if(g[i][j] == 'X') { walls_col[j].push_back(i); } } walls_col[j].push_back(n); } vp dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; vector<vb> canReach(n, vb(m, false)); canReach[sx][sy] = true; qp q; q.push({sx, sy}); while(q.size()) { if(canReach[ex][ey]) break; auto[x, y] = q.front(); q.pop(); ll up, down, left, right; auto it = lower_bound(all(walls_row[x]), y); right = *it; it--; left = *it; it = lower_bound(all(walls_col[y]), x); down = *it; it--; up = *it; for(auto[dirX, dirY] : dirs) { ll newX = x + dirX, newY = y + dirY; if(newX < 0 || newX >= n || newY < 0 || newY >= m) continue; if(g[newX][newY] == 'X' || canReach[newX][newY]) continue; bool can = true; ll up2, down2, left2, right2; auto it = lower_bound(all(walls_row[newX]), newY); right2 = *it; it--; left2 = *it; it = lower_bound(all(walls_col[newY]), newX); down2 = *it; it--; up2 = *it; ll l = max(left, left2); ll r = min(right, right2); if(r - l - 1 < hor) can = false; l = max(up, up2); r = min(down, down2); if(r - l - 1 < vert) can = false; if(!can) continue; canReach[newX][newY] = true; q.push({newX, newY}); } } if(canReach[ex][ey]) cout << "YES\n"; else cout << "NO\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...