oj.uz

Submission #1100629

# Submission time Handle Problem Language Result Execution time Memory
1100629 2024-10-14T10:44:58 Z crafticat Toy (CEOI24_toy) C++17
0 / 100
 1500 ms 634608 KB 
#include <bits/stdc++.h>

using namespace std;
template<typename T>
using V = vector<T>;

int w, h, k, l;
V<V<V<V<bool>>>> vis;
V<V<bool>> grid;
int dx[] = {0,1,-1,0};
int dy[] = {1,0,0,-1};
int visA = 0;

bool outOfB(int x, int y) {
    if (x >= w || y >= h || x < 0 || y < 0) return true;
    return false;
}

bool validPosition(int x, int y, int x2, int y2) {
    for (int i = x; i < x + k; ++i) {
        if (outOfB(i,y)) return false;
        if (!grid[i][y]) return false;
    }
    for (int i = y2; i < y2 + l; ++i) {
        if (outOfB(x2,i)) return false;
        if (!grid[x2][i]) return false;
    }
    return true;
}

void bfs(int x, int y, int x2 ,int y2) {
    if (!validPosition(x, y, x2, y2)) return;
    if (vis[x][y][x2][y2]) return;
    vis[x][y][x2][y2] = true;
    visA++;

    for (int i = 0; i < 4; ++i) {
        bfs(x + dx[i], y + dy[i], x2,y2);
    }
    for (int i = 0; i < 4; ++i) {
        bfs(x, y, x2 + dx[i],y2 + dy[i]);
    }
}

int main() {
    cin >> w >> h >> k >> l;

    int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
    int targetX, targetY;

    vis.resize(w, V<V<V<bool>>>(h,V<V<bool>>(w, V<bool>(h))));
    grid.resize(w, V<bool>(h));

    for (int i = 0; i < h; ++i) {
        string str; cin >> str;
        for (int j = 0; j < w; ++j) {
            grid[j][i] = str[j] != 'X';
            if (str[j] == '*') {
                targetX = j;
                targetY = i;
            }
        }
    }

    for (int i = targetX - k + 1; i <= targetX; ++i) {
        for (int j = i; j < i + k; ++j) {
            for (int m = targetY - l + 1; m <= targetY; ++m) {
                bfs(i, targetY, j, m);
            }
        }
    }

    for (int i = targetY - l + 1; i <= targetY; ++i) {
        for (int j = i; j < i + l; ++j) {
            for (int m = targetX - k + 1; m <= targetX; ++m) {
                bfs(m,j,targetX,i );
            }
        }
    }

    if (visA == 1) {
        cout << "NO";
        return 0;
    }
    cout << (vis[x1][y1][x2][y2] ? "YES" : "NO");

    return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:73:37: warning: 'targetY' may be used uninitialized in this function [-Wmaybe-uninitialized]
   73 |     for (int i = targetY - l + 1; i <= targetY; ++i) {
      |                                   ~~^~~~~~~~~~
Main.cpp:49:9: warning: 'targetX' may be used uninitialized in this function [-Wmaybe-uninitialized]
   49 |     int targetX, targetY;
      |         ^~~~~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct

Subtask #1
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 8 ms 2132 KB Output is correct
4 Correct 1417 ms 216140 KB Output is correct
5 Correct 39 ms 9548 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 63 ms 10136 KB Output is correct
8 Correct 35 ms 9292 KB Output is correct
9 Correct 5 ms 2296 KB Output is correct
10 Correct 30 ms 9336 KB Output is correct
11 Correct 30 ms 9292 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 30 ms 9380 KB Output is correct
14 Correct 30 ms 9300 KB Output is correct
15 Incorrect 1105 ms 157124 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #2
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 8 ms 2132 KB Output is correct
4 Correct 1417 ms 216140 KB Output is correct
5 Correct 39 ms 9548 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 63 ms 10136 KB Output is correct
8 Correct 35 ms 9292 KB Output is correct
9 Correct 5 ms 2296 KB Output is correct
10 Correct 30 ms 9336 KB Output is correct
11 Correct 30 ms 9292 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 30 ms 9380 KB Output is correct
14 Correct 30 ms 9300 KB Output is correct
15 Incorrect 1105 ms 157124 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Execution timed out 1573 ms 634608 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 8 ms 2132 KB Output is correct
4 Correct 1417 ms 216140 KB Output is correct
5 Correct 39 ms 9548 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 63 ms 10136 KB Output is correct
8 Correct 35 ms 9292 KB Output is correct
9 Correct 5 ms 2296 KB Output is correct
10 Correct 30 ms 9336 KB Output is correct
11 Correct 30 ms 9292 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 30 ms 9380 KB Output is correct
14 Correct 30 ms 9300 KB Output is correct
15 Incorrect 1105 ms 157124 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 8 ms 2132 KB Output is correct
4 Correct 1417 ms 216140 KB Output is correct
5 Correct 39 ms 9548 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 63 ms 10136 KB Output is correct
8 Correct 35 ms 9292 KB Output is correct
9 Correct 5 ms 2296 KB Output is correct
10 Correct 30 ms 9336 KB Output is correct
11 Correct 30 ms 9292 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 30 ms 9380 KB Output is correct
14 Correct 30 ms 9300 KB Output is correct
15 Incorrect 1105 ms 157124 KB Output isn't correct
16 Halted 0 ms 0 KB -