Submission #1053453

#TimeUsernameProblemLanguageResultExecution timeMemory
1053453elazarkorenToy (CEOI24_toy)C++17
9 / 100
6 ms13148 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #define x first #define y second #define all(v) v.begin(), v.end() #define chkmin(a, b) a = min(a, b) #define chkmax(a, b) a = max(a, b) using namespace std; typedef long long ll; typedef vector<ll> vi; typedef vector<vi> vvi; typedef pair<ll, ll> pii; typedef vector<pii> vii; typedef vector<bool> vb; typedef vector<vb> vvb; const int MAX_N = 1505; int dx[] = {0, 0, -1, 1}, dy[] = {1, -1, 0, 0}; int dp_u[MAX_N][MAX_N], dp_d[MAX_N][MAX_N], dp_l[MAX_N][MAX_N], dp_r[MAX_N][MAX_N]; int n, m, k, l; bool Check(int x, int y, int nx, int ny) { if (x == nx) { int u = max(dp_u[x][y], dp_u[nx][ny]); int d = min(dp_d[x][y], dp_d[nx][ny]); return d - u + 1 >= k; } int le = max(dp_l[x][y], dp_l[nx][ny]); int r = min(dp_r[x][y], dp_r[nx][ny]); return r - le + 1 >= l; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cin >> m >> n >> k >> l; int xh, yh, xv, yv, xt, yt; cin >> xh >> yh >> xv >> yv; vvb visited(n, vb(m)); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { char c; cin >> c; if (c == '*') { xt = i, yt = j; } else if (c == 'X') visited[i][j] = 1; } } for (int i = 1; i < n; i++) { for (int j = 0; j < m; j++) { dp_u[i][j] = visited[i - 1][j] ? i : dp_u[i - 1][j]; } } for (int j = 0; j < m; j++) dp_d[n - 1][j] = n - 1; for (int i = n - 2; i >= 0; i--) { for (int j = 0; j < m; j++) { dp_d[i][j] = visited[i + 1][j] ? i : dp_d[i + 1][j]; } } for (int i = 0; i < n; i++) { for (int j = 1; j < m; j++) { dp_l[i][j] = visited[i][j - 1] ? j : dp_l[i][j - 1]; } } for (int i = 0; i < n; i++) dp_r[i][m - 1] = m - 1; for (int i = 0; i < n; i++) { for (int j = m - 2; j >= 0; j--) { dp_r[i][j] = visited[i][j + 1] ? j : dp_r[i][j + 1]; } } queue<pii> q; q.push({yh, xv}); visited[yh][xv] = 1; while (!q.empty()) { auto [x, y] = q.front(); q.pop(); for (int d = 0; d < 4; d++) { int nx = x + dx[d], ny = y + dy[d]; if (0 > nx || nx >= n || 0 > ny || ny >= m || visited[nx][ny]) continue; if (Check(x, y, nx, ny)) { q.push({nx, ny}); visited[nx][ny] = 1; } } } cout << (visited[xt][yt] ? "YES\n" : "NO\n"); }

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:88:24: warning: 'xt' may be used uninitialized in this function [-Wmaybe-uninitialized]
   88 |     cout << (visited[xt][yt] ? "YES\n" : "NO\n");
      |                        ^
#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...