oj.uz

Submission #1004444

# Submission time Handle Problem Language Result Execution time Memory
1004444 2024-06-21T09:04:18 Z Nailuj_217 Furniture (JOI20_furniture) C++17
5 / 100
 5000 ms 7108 KB 
#include <bits/stdc++.h>
#define l long long
using namespace std;

const l LEN = 1005;
l n, m;

array<array<bool, LEN>, LEN> grid;
array<array<bool, LEN>, LEN> possible, visited, updatepossible;

bool dfs(l x, l y) {
    if (visited[x][y]) return possible[x][y];
    visited[x][y] = true;
    if (grid[x][y]) return possible[x][y] = false;
    if (x == n && y == m) return possible[x][y] = true;
    if (x != n)
        if (dfs(x+1, y)) possible[x][y] = true;
    if (y != m) 
        if (dfs(x, y+1)) possible[x][y] = true;

    return possible[x][y];
}

bool dfsback(l x, l y) {
    if (!updatepossible[x][y]) return false;
    if (grid[x][y]) return false;
    
    if (x != n && updatepossible[x+1][y]) return true;
    if (y != m && updatepossible[x][y+1]) return true;
    updatepossible[x][y] = false;
    bool isval = false;
    if (x != 1 && dfsback(x-1, y)) isval = true;
    if (y != 1 && dfsback(x, y-1)) isval = true;
    return isval;
}



int main() {


    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> grid[i][j];


    dfs(1, 1);

    l q, x, y;
    bool left, top;
    cin >> q;
    while (q--) {
        cin >> x >> y;
        if (!possible[x][y]) {
            grid[x][y] = true;
            cout << 1 << "\n";
            continue;
        }
        updatepossible = possible;
        updatepossible[x][y] = false;
        if (x != 1) dfsback(x-1, y);
        if (y != 1) dfsback(x, y-1);
        if (x != 1) dfsback(x-1, y);
        // if (top || left) {
        //     if (x != 1 && top) top = dfsback(x-1, y);
        //     if (y != 1 && left) left = dfsback(x, y-1);
        // }
        if (updatepossible[1][1]) {
            possible = updatepossible;
            grid[x][y] = true;
            cout << 1 << "\n";
        } else {
            cout << 0 << "\n";
        }




    }

    return 0;
}

Compilation message

furniture.cpp: In function 'int main()':
furniture.cpp:51:10: warning: unused variable 'left' [-Wunused-variable]
   51 |     bool left, top;
      |          ^~~~
furniture.cpp:51:16: warning: unused variable 'top' [-Wunused-variable]
   51 |     bool left, top;
      |                ^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 2396 KB Output is correct
2 Correct 27 ms 2648 KB Output is correct
3 Correct 71 ms 2396 KB Output is correct
4 Correct 92 ms 2652 KB Output is correct
5 Correct 111 ms 2940 KB Output is correct
6 Correct 183 ms 2684 KB Output is correct
7 Correct 76 ms 2652 KB Output is correct
8 Correct 308 ms 2648 KB Output is correct
9 Correct 187 ms 2652 KB Output is correct

Subtask #2
0.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 2396 KB Output is correct
2 Correct 27 ms 2648 KB Output is correct
3 Correct 71 ms 2396 KB Output is correct
4 Correct 92 ms 2652 KB Output is correct
5 Correct 111 ms 2940 KB Output is correct
6 Correct 183 ms 2684 KB Output is correct
7 Correct 76 ms 2652 KB Output is correct
8 Correct 308 ms 2648 KB Output is correct
9 Correct 187 ms 2652 KB Output is correct
10 Correct 89 ms 2652 KB Output is correct
11 Correct 124 ms 2392 KB Output is correct
12 Execution timed out 5065 ms 7108 KB Time limit exceeded
13 Halted 0 ms 0 KB -