oj.uz

Submission #924714

# Submission time Handle Problem Language Result Execution time Memory
924714 2024-02-09T14:27:25 Z boris_mihov Furniture (JOI20_furniture) C++17
100 / 100
 248 ms 26864 KB 
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <queue>
#include <cmath>
#include <set>
 
typedef long long llong;
const int MAXN = 1000 + 10;
const int INF  = 1e9;
 
int n, m, q;
int a[MAXN][MAXN];
int b[MAXN][MAXN];
int e[MAXN][MAXN];
int cntWithB[2 * MAXN];

bool empty[MAXN][MAXN];
std::vector <std::pair <int,int>> deltaB = {{1, 0}, {0, 1}};
std::vector <std::pair <int,int>> deltaE = {{-1, 0}, {0, -1}};

bool inside(int row, int col)
{
    return (row >= 1 && row <= n && col >= 1 && col <= m);
}

bool checkCell(int row, int col, std::vector <std::pair <int,int>> &delta, int d[][MAXN])
{
    int cnt = 0;
    for (const auto &[dx, dy] : delta)
    {
        if (inside(row - dx, col - dy) && d[row - dx][col - dy] == d[row][col] - 1 && !empty[row - dx][col - dy])
        {
            cnt++;
        }
    }

    return cnt == 0;
}

void runBFS(int row, int col, std::vector <std::pair <int,int>> &delta, int d[][MAXN])
{
    std::vector <std::pair <int,int>> toErase;
    std::queue <std::pair <int,int>> q;
    q.push({row, col});

    while (q.size())
    {
        auto [currR, currC] = q.front();
        toErase.push_back({currR, currC});
        if (!empty[currR][currC])
        {
            cntWithB[b[currR][currC]]--;
        }

        empty[currR][currC] = true;
        q.pop();
        
        for (const auto &[dx, dy] : delta)
        {
            if (!inside(currR + dx, currC + dy) || empty[currR + dx][currC + dy] || !checkCell(currR + dx, currC + dy, delta, d))
            {
                continue;
            }

            q.push({currR + dx, currC + dy});
        }
    }
}

bool destroy(int row, int col)
{
    if (empty[row][col])
    {
        return true;
    }

    if (cntWithB[b[row][col]] == 1)
    {
        return false;
    }

    runBFS(row, col, deltaB, b);
    runBFS(row, col, deltaE, e);
    return true;
}

void solve()
{
    for (int i = 1 ; i <= n ; ++i)
    {
        for (int j = 1 ; j <= m ; ++j)
        {
            b[i][j] = i - 1 + j - 1;
            e[i][j] = n - i + m - j;
            cntWithB[b[i][j]]++;
        }
    }

    for (int i = 1 ; i <= n ; ++i)
    {
        for (int j = 1 ; j <= m ; ++j)
        {
            if (a[i][j] == 1)
            {
                destroy(i, j);
            }
        }
    }

    for (int i = 1 ; i <= q ; ++i)
    {
        int row, col;
        std::cin >> row >> col;
        std::cout << destroy(row, col) << '\n';
    }
}
 
void input()
{
    std::cin >> n >> m;
    for (int i = 1 ; i <= n ; ++i)
    {
        for (int j = 1 ; j <= m ; ++j)
        {
            std::cin >> a[i][j];
        }
    }

    std::cin >> q;
}
 
void fastIOI()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}
 
int main()
{
    fastIOI();
    input();
    solve();
 
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 2 ms 6900 KB Output is correct
3 Correct 2 ms 6748 KB Output is correct
4 Correct 3 ms 6756 KB Output is correct
5 Correct 3 ms 6748 KB Output is correct
6 Correct 5 ms 6628 KB Output is correct
7 Correct 3 ms 6748 KB Output is correct
8 Correct 3 ms 6748 KB Output is correct
9 Correct 3 ms 6748 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 2 ms 6900 KB Output is correct
3 Correct 2 ms 6748 KB Output is correct
4 Correct 3 ms 6756 KB Output is correct
5 Correct 3 ms 6748 KB Output is correct
6 Correct 5 ms 6628 KB Output is correct
7 Correct 3 ms 6748 KB Output is correct
8 Correct 3 ms 6748 KB Output is correct
9 Correct 3 ms 6748 KB Output is correct
10 Correct 9 ms 7004 KB Output is correct
11 Correct 3 ms 6748 KB Output is correct
12 Correct 140 ms 18172 KB Output is correct
13 Correct 70 ms 15164 KB Output is correct
14 Correct 223 ms 22704 KB Output is correct
15 Correct 219 ms 23056 KB Output is correct
16 Correct 215 ms 23696 KB Output is correct
17 Correct 206 ms 24412 KB Output is correct
18 Correct 227 ms 24144 KB Output is correct
19 Correct 248 ms 25708 KB Output is correct
20 Correct 223 ms 26864 KB Output is correct
21 Correct 224 ms 26744 KB Output is correct