| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1070513 |
2024-08-22T14:54:18 Z |
Alebn |
Toy (CEOI24_toy) |
C++14 |
|
10 ms |
4952 KB |
#include <bits/stdc++.h>
#define int long long
using namespace std;
struct S {
int x, y;
S(){}
S(int xi, int yi):x(xi),y(yi){}
};
int sum(vector<vector<int>>& prefix, int x1, int y1, int x2, int y2) {
return prefix[x2][y2] - (x1 > 0 ? prefix[x1 - 1][y2] : 0) - (y1 > 0 ? prefix[x2][y1 - 1] : 0) + (x1 > 0 && y1 > 0 ? prefix[x1 - 1][y1 - 1] : 0);
}
int add(vector<vector<int>>& prefix, int i, int j) {
return prefix[i][j] + (i > 0 ? prefix[i - 1][j] : 0) + (j > 0 ? prefix[i][j - 1] : 0) - (i > 0 && j > 0 ? prefix[i - 1][j - 1] : 0);
}
void solve() {
int n, m, k, l, xh, yh, xv, yv, endx, endy;
cin >> m >> n >> l >> k >> yh >> xh >> yv >> xv;
vector<string> arr(n);
vector<vector<int>> prefix(n, vector<int>(m));
for(int i = 0; i < n; i++) {
cin >> arr[i];
for(int j = 0; j < m; j++) {
prefix[i][j] = (arr[i][j] == 'X') + add(prefix, i, j);
if(arr[i][j] == '*') endx = i, endy = j;
}
}
vector<vector<int>> up(n, vector<int>(m)), down(n, vector<int>(m)), right(n, vector<int>(m)), left(n, vector<int>(m));
// calculate for hori
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(i > 0 && j > l - 2 && sum(prefix, i - 1, j - l + 1, i, j) == 0) {
down[i - 1][j - l + 1]++;
if(j < m - 2) down[i - 1][j + 1]--;
up[i][j - l + 1]++;
if(j < m - 2) up[i][j + 1]--;
}
if(i > k - 2 && j > 0 && sum(prefix, i - k + 1, j - 1, i, j) == 0) {
right[i - k + 1][j - 1]++;
if(i < n - 2) down[i + 1][j - 1]--;
left[i - k + 1][j]++;
if(i < n - 2) left[i + 1][j]--;
}
}
}
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
up[i][j] += (j > 0 ? up[i][j - 1] : 0);
down[i][j] += (j > 0 ? down[i][j - 1] : 0);
right[i][j] += (i > 0 ? right[i - 1][j] : 0);
left[i][j] += (i > 0 ? left[i - 1][j] : 0);
}
}
queue<S> q;
vector<vector<int>> visited(n, vector<int>(m, false));
q.push(S(xh, yv));
while(q.size()) {
S temp = q.front();
q.pop();
if(visited[temp.x][temp.y]) continue;
visited[temp.x][temp.y] = true;
if(up[temp.x][temp.y]) q.push(S(temp.x - 1, temp.y));
if(down[temp.x][temp.y]) q.push(S(temp.x + 1, temp.y));
if(right[temp.x][temp.y]) q.push(S(temp.x, temp.y + 1));
if(left[temp.x][temp.y]) q.push(S(temp.x, temp.y - 1));
}
if(visited[endx][endy]) cout << "YES\n";
else cout << "NO\n";
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
solve();
}
Compilation message
Main.cpp: In function 'void solve()':
Main.cpp:69:26: warning: 'endy' may be used uninitialized in this function [-Wmaybe-uninitialized]
69 | if(visited[endx][endy]) cout << "YES\n";
| ^
Main.cpp:69:20: warning: 'endx' may be used uninitialized in this function [-Wmaybe-uninitialized]
69 | if(visited[endx][endy]) cout << "YES\n";
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
344 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
1 ms |
348 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Correct |
0 ms |
348 KB |
Output is correct |
| 11 |
Correct |
0 ms |
348 KB |
Output is correct |
| 12 |
Correct |
0 ms |
348 KB |
Output is correct |
| 13 |
Correct |
0 ms |
348 KB |
Output is correct |
| 14 |
Correct |
1 ms |
348 KB |
Output is correct |
| 15 |
Correct |
0 ms |
348 KB |
Output is correct |
| 16 |
Correct |
0 ms |
348 KB |
Output is correct |
| 17 |
Correct |
1 ms |
344 KB |
Output is correct |
| 18 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 19 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
344 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
1 ms |
348 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Correct |
0 ms |
348 KB |
Output is correct |
| 11 |
Correct |
0 ms |
348 KB |
Output is correct |
| 12 |
Correct |
0 ms |
348 KB |
Output is correct |
| 13 |
Correct |
0 ms |
348 KB |
Output is correct |
| 14 |
Correct |
1 ms |
348 KB |
Output is correct |
| 15 |
Correct |
0 ms |
348 KB |
Output is correct |
| 16 |
Correct |
0 ms |
348 KB |
Output is correct |
| 17 |
Correct |
1 ms |
344 KB |
Output is correct |
| 18 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 19 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
604 KB |
Output is correct |
| 4 |
Correct |
6 ms |
4700 KB |
Output is correct |
| 5 |
Correct |
10 ms |
4700 KB |
Output is correct |
| 6 |
Correct |
1 ms |
860 KB |
Output is correct |
| 7 |
Correct |
10 ms |
4844 KB |
Output is correct |
| 8 |
Correct |
7 ms |
4952 KB |
Output is correct |
| 9 |
Correct |
3 ms |
1884 KB |
Output is correct |
| 10 |
Correct |
3 ms |
4696 KB |
Output is correct |
| 11 |
Correct |
4 ms |
4700 KB |
Output is correct |
| 12 |
Correct |
1 ms |
1880 KB |
Output is correct |
| 13 |
Correct |
3 ms |
4700 KB |
Output is correct |
| 14 |
Correct |
3 ms |
4700 KB |
Output is correct |
| 15 |
Correct |
6 ms |
4616 KB |
Output is correct |
| 16 |
Incorrect |
7 ms |
4184 KB |
Output isn't correct |
| 17 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
344 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
1 ms |
348 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Correct |
0 ms |
348 KB |
Output is correct |
| 11 |
Correct |
0 ms |
348 KB |
Output is correct |
| 12 |
Correct |
0 ms |
348 KB |
Output is correct |
| 13 |
Correct |
0 ms |
348 KB |
Output is correct |
| 14 |
Correct |
1 ms |
348 KB |
Output is correct |
| 15 |
Correct |
0 ms |
348 KB |
Output is correct |
| 16 |
Correct |
0 ms |
348 KB |
Output is correct |
| 17 |
Correct |
1 ms |
344 KB |
Output is correct |
| 18 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 19 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
344 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
1 ms |
348 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Correct |
0 ms |
348 KB |
Output is correct |
| 11 |
Correct |
0 ms |
348 KB |
Output is correct |
| 12 |
Correct |
0 ms |
348 KB |
Output is correct |
| 13 |
Correct |
0 ms |
348 KB |
Output is correct |
| 14 |
Correct |
1 ms |
348 KB |
Output is correct |
| 15 |
Correct |
0 ms |
348 KB |
Output is correct |
| 16 |
Correct |
0 ms |
348 KB |
Output is correct |
| 17 |
Correct |
1 ms |
344 KB |
Output is correct |
| 18 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 19 |
Halted |
0 ms |
0 KB |
- |
