Submission #1142305

#	Time	Username	Problem	Language	Result	Execution time	Memory
1142305		Sharky	Furniture (JOI20_furniture)	C++20	100 / 100	338 ms	22240 KiB

furniture

#include <bits/stdc++.h>
using namespace std;

const int dx[4] = {0, 1, -1, 0}, dy[4] = {1, 0, 0, -1};

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m;
    cin >> n >> m;
    vector<vector<int>> g(n+1, vector<int> (m+1, 0)), f(n+2, vector<int> (m+2, 0));
    vector<array<int, 3>> qu;
    map<int, int> cnt;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> g[i][j];
            f[i][j] = 1;
            cnt[i + j]++;
            if (g[i][j]) qu.push_back({i, j, 0});
        }
    }
    int q;
    cin >> q;
    while (q--) {
        int r, c;
        cin >> r >> c;
        qu.push_back({r, c, 1});
    }
    for (auto& [sr, sc, out] : qu) {
        if (cnt[sr + sc] == 1 && f[sr][sc]) {
            // cout << sr << " " << sc << " cnt\n";
            if (out) cout << "0\n";
            continue;
        }
        // if (f[sr][sc]) {
        //     // cout << sr << " " << sc << " f\n";
        //     if (out) cout << "Yes\n";
        //     continue;
        // }
        queue<pair<int, int>> bfs;
        bfs.push({sr, sc});
        if (f[sr][sc]) cnt[sr + sc]--;
        f[sr][sc] = 0;
        while (!bfs.empty()) {
            auto [r, c] = bfs.front();
            bfs.pop();
            // cout << "hi " << r << " " << c < '\n';
            for (int i = 0; i < 4; i++) {
                int x = r + dx[i], y = c + dy[i];
                if (x < 1 || x > n || y < 1 || y > m) continue;
                if ((((x != n || y != m) && !f[x+1][y] && !f[x][y+1]) || ((x != 1 || y != 1) && !f[x-1][y] && !f[x][y-1])) && f[x][y]) {
                    f[x][y] = 0;
                    cnt[x + y]--;
                    bfs.push({x, y});
                }
            }
        }
        if (out) cout << "1\n";
        // for (int i = 1; i <= n; i++) {
        //     for (int j = 1; j <= m; j++) cout << f[i][j] << " ";
        //     cout << '\n';
        // }
    }
}

• Subtask 1: 5 / 5
• Subtask 2: 95 / 95