oj.uz

Submission #1004446

# Submission time Handle Problem Language Result Execution time Memory
1004446 2024-06-21T09:05:25 Z Nailuj_217 Furniture (JOI20_furniture) C++17
5 / 100
 5000 ms 6664 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() {

    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    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:53:10: warning: unused variable 'left' [-Wunused-variable]
   53 |     bool left, top;
      |          ^~~~
furniture.cpp:53:16: warning: unused variable 'top' [-Wunused-variable]
   53 |     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 25 ms 2652 KB Output is correct
3 Correct 63 ms 2648 KB Output is correct
4 Correct 92 ms 2696 KB Output is correct
5 Correct 104 ms 2652 KB Output is correct
6 Correct 185 ms 2648 KB Output is correct
7 Correct 64 ms 2648 KB Output is correct
8 Correct 343 ms 2648 KB Output is correct
9 Correct 173 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 25 ms 2652 KB Output is correct
3 Correct 63 ms 2648 KB Output is correct
4 Correct 92 ms 2696 KB Output is correct
5 Correct 104 ms 2652 KB Output is correct
6 Correct 185 ms 2648 KB Output is correct
7 Correct 64 ms 2648 KB Output is correct
8 Correct 343 ms 2648 KB Output is correct
9 Correct 173 ms 2652 KB Output is correct
10 Correct 60 ms 2896 KB Output is correct
11 Correct 115 ms 2392 KB Output is correct
12 Execution timed out 5032 ms 6664 KB Time limit exceeded
13 Halted 0 ms 0 KB -