Submission #956191

#	Time	Username	Problem	Language	Result	Execution time	Memory
956191		LucaIlie	Furniture (JOI20_furniture)	C++17	100 / 100	175 ms	14104 KiB

furniture

#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 / 5
• Subtask 2: 95 / 95