oj.uz

Submission #1004457

# Submission time Handle Problem Language Result Execution time Memory
1004457 2024-06-21T09:12:15 Z Nailuj_217 Furniture (JOI20_furniture) C++17
5 / 100
 5000 ms 7252 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;
    l a;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            cin >> a;
            grid[i][j] = a;

        }


    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;
}
/*
6 8
0 0 0 0 0 0 0 0  
0 1 0 0 0 0 1 0
0 1 0 0 1 1 1 0
0 1 0 0 1 0 1 0
0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0
100
4 6
1 2
6 1
5 1
4 1
3 1
2 1
6 2
6 3
4 3
4 4
4 8
5 8




6 8
0 0 0 0 0 0 0 0  
0 1 0 0 0 0 1 0
0 1 0 0 1 1 1 0
0 1 0 0 1 0 1 0
0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0
100



6 6
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
100
2 2
1
3 2
1
4 2
1
5 2
1
5 1
1
4 1
1
3 1
1
2 1
1
1 4
1
2 4
1
2 5
1
1 5
1
4 4
1
3 3
0
4 5
1
5 4
1
5 5
0

*/

Compilation message

furniture.cpp: In function 'int main()':
furniture.cpp:56:10: warning: unused variable 'left' [-Wunused-variable]
   56 |     bool left, top;
      |          ^~~~
furniture.cpp:56:16: warning: unused variable 'top' [-Wunused-variable]
   56 |     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 23 ms 2648 KB Output is correct
3 Correct 64 ms 2652 KB Output is correct
4 Correct 90 ms 2696 KB Output is correct
5 Correct 106 ms 2652 KB Output is correct
6 Correct 184 ms 2716 KB Output is correct
7 Correct 65 ms 2716 KB Output is correct
8 Correct 331 ms 2960 KB Output is correct
9 Correct 183 ms 2648 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 23 ms 2648 KB Output is correct
3 Correct 64 ms 2652 KB Output is correct
4 Correct 90 ms 2696 KB Output is correct
5 Correct 106 ms 2652 KB Output is correct
6 Correct 184 ms 2716 KB Output is correct
7 Correct 65 ms 2716 KB Output is correct
8 Correct 331 ms 2960 KB Output is correct
9 Correct 183 ms 2648 KB Output is correct
10 Correct 59 ms 2900 KB Output is correct
11 Correct 111 ms 2592 KB Output is correct
12 Execution timed out 5043 ms 7252 KB Time limit exceeded
13 Halted 0 ms 0 KB -