oj.uz

Submission #956191

# Submission time Handle Problem Language Result Execution time Memory
956191 2024-04-01T09:27:19 Z LucaIlie Furniture (JOI20_furniture) C++17
100 / 100
 175 ms 14104 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e3;
const int MAX_M = 1e3;
bool isBlocked[MAX_N + 2][MAX_M + 2], isPath[MAX_N + 2][MAX_M + 2];
int countDiagPaths[MAX_N + MAX_M + 1];

void updateIsPath( int l, int c ) {
    if ( !isPath[l][c] )
        return;

    if ( !isBlocked[l][c] && (isPath[l][c - 1] || isPath[l - 1][c]) && (isPath[l][c + 1] || isPath[l + 1][c]) )
        return;


    isPath[l][c] = false;
    countDiagPaths[l + c]--;

    updateIsPath( l, c - 1 );
    updateIsPath( l - 1, c );
    updateIsPath( l, c + 1 );
    updateIsPath( l + 1, c );
}

int main() {
    cin.tie( NULL );
    ios_base::sync_with_stdio( false );

    int n, m;

    cin >> n >> m;

    isPath[0][1] = isPath[1][0] = isPath[n][m + 1] = isPath[n + 1][m] = true;
    for ( int l = 1; l <= n; l++ ) {
        for ( int c = 1; c <= m; c++ ) {
            isPath[l][c] = true;
            countDiagPaths[l + c]++;
        }
    }
    for ( int l = 1; l <= n; l++ ) {
        for ( int c = 1; c <= m; c++ ) {
            int x;
            cin >> x;
            if ( x ) {
                isBlocked[l][c] = true;
                updateIsPath( l, c );
            }
        }
    }

    int q;
    cin >> q;
    for ( int i = 0; i < q; i++ ) {
        int l, c;
        cin >> l >> c;

        if ( countDiagPaths[l + c] == isPath[l][c] )
            cout << "0\n";
        else {
            cout << "1\n";
            isBlocked[l][c] = true;
            updateIsPath( l, c );
        }
    }

    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 472 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 3 ms 604 KB Output is correct
6 Correct 2 ms 652 KB Output is correct
7 Correct 3 ms 604 KB Output is correct
8 Correct 2 ms 648 KB Output is correct
9 Correct 2 ms 604 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 472 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 3 ms 604 KB Output is correct
6 Correct 2 ms 652 KB Output is correct
7 Correct 3 ms 604 KB Output is correct
8 Correct 2 ms 648 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 6 ms 860 KB Output is correct
11 Correct 2 ms 472 KB Output is correct
12 Correct 91 ms 7056 KB Output is correct
13 Correct 47 ms 4180 KB Output is correct
14 Correct 146 ms 11720 KB Output is correct
15 Correct 154 ms 12088 KB Output is correct
16 Correct 154 ms 12880 KB Output is correct
17 Correct 173 ms 13668 KB Output is correct
18 Correct 175 ms 13308 KB Output is correct
19 Correct 166 ms 13904 KB Output is correct
20 Correct 163 ms 14104 KB Output is correct
21 Correct 172 ms 13976 KB Output is correct