| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1087839 |
2024-09-13T10:05:38 Z |
mychecksedad |
Toy (CEOI24_toy) |
C++17 |
|
2 ms |
860 KB |
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define en cout << '\n'
#define vi vector<int>
#define pii pair<int, int>
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
const int N = 1500+100;
int n, m, k, l, xh, yh, xv, yv, pref[N][N], H[N][N], V[N][N], vis[N][N], L[N][N], R[N][N], U[N][N], D[N][N];
string s[N];
int arr[4][2]={
{0, 1},
{1, 0},
{-1, 0},
{0, -1}
};
int get(int r1, int r2, int c1, int c2){
return pref[r2][c2] - pref[r1 - 1][c2] - pref[r2][c1 - 1] + pref[r1 - 1][c1 - 1];
}
void solve(){
cin >> m >> n >> k >> l;
cin >> yh >> xh >> yv >> xv;
++xh, ++yh, ++xv, ++yv;
for(int i = 1; i <= n; ++i){
cin >> s[i];
s[i] = " " + s[i];
}
for(int i = 0; i <= n; ++i) for(int j = 0; j <= m; ++j) pref[i][j] = 0;
for(int i = 0; i <= n; ++i) for(int j = 0; j <= m; ++j) H[i][j] = V[i][j] = vis[i][j] = L[i][j] = R[i][j] = D[i][j] = U[i][j] = 0;
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= m; ++j){
pref[i][j] = pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1];
if(s[i][j] == 'X') ++pref[i][j];
}
}
H[xh][yh] = 1;
queue<pii> q;
q.push({xh, yh});
while(!q.empty()){
int x = q.front().ff;
int y = q.front().ss;
q.pop();
for(int i = 0; i < 4; ++i){
int nx = x + arr[i][0];
int ny = y + arr[i][1];
if(nx > 0 && ny > 0 && nx <= n && ny + k - 1 <= m && H[nx][ny] == 0){
if(get(nx, nx, ny, ny + k - 1) == 0){
H[nx][ny] = 1;
q.push({nx, ny});
}
}
}
}
V[xv][yv] = 1;
q.push({xv, yv});
while(!q.empty()){
int x = q.front().ff;
int y = q.front().ss;
q.pop();
for(int i = 0; i < 4; ++i){
int nx = x + arr[i][0];
int ny = y + arr[i][1];
if(nx > 0 && ny > 0 && nx + l - 1 <= n && ny <= m && V[nx][ny] == 0){
if(get(nx, nx+l-1, ny, ny) == 0){
V[nx][ny] = 1;
q.push({nx, ny});
}
}
}
}
for(int i = n; i >= 1; --i){
for(int j = m; j >= 1; --j){
for(int i1 = i; i1 >= i - l + 1; --i1)
if(get(i1, i, j, j) == 0 && V[i1][j]){
if(V[i1][j + 1]) R[i][j] = 1;
if(V[i1][j - 1]) L[i][j] = 1;
}
for(int i1 = j; i1 >= j - k + 1; --i1)
if(get(i, i, i1, j) == 0 && H[i][i1]){
if(H[i - 1][i1]) U[i][j] = 1;
if(H[i + 1][i1]) D[i][j] = 1;
}
}
}
// for(int i = 1; i <= n; ++i){
// for(int j = 1; j <= m; ++j){
// cout << L[i][j];
// }
// en;
// }
assert(H[xh][yv] && V[xh][yv]);
vis[xh][yv] = 1;
q.push({xh, yv});
while(!q.empty()){
int x = q.front().ff;
int y = q.front().ss;
q.pop();
for(int i = 0; i < 4; ++i){
int nx = x + arr[i][0];
int ny = y + arr[i][1];
if(nx > 0 && ny > 0 && nx <= n && ny <= m && !vis[nx][ny]){
if((nx == x - 1 && L[x][y]) || (nx == x + 1 && R[x][y]) || (ny == y + 1 && D[x][y]) || (ny == y - 1 && U[x][y])){
vis[nx][ny] = 1;
q.push({nx, ny});
}
}
}
}
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= m; ++j){
if(s[i][j] == '*' && vis[i][j]){
cout << "YES";
return;
}
}
}
cout << "NO";
}
int main(){
cin.tie(0); ios::sync_with_stdio(0);
solve();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
604 KB |
Output is correct |
| 2 |
Runtime error |
2 ms |
860 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
604 KB |
Output is correct |
| 2 |
Runtime error |
2 ms |
860 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
604 KB |
Output is correct |
| 2 |
Runtime error |
2 ms |
860 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
604 KB |
Output is correct |
| 2 |
Runtime error |
2 ms |
860 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
604 KB |
Output is correct |
| 2 |
Runtime error |
2 ms |
860 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
604 KB |
Output is correct |
| 2 |
Runtime error |
2 ms |
860 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
