QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#134677#2446. Block Breakerckiseki#AC ✓135ms27128kbC++142.0kb2023-08-04 14:45:512023-08-04 14:45:52

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-04 14:45:52]
  • 评测
  • 测评结果:AC
  • 用时:135ms
  • 内存:27128kb
  • [2023-08-04 14:45:51]
  • 提交

answer

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

#define all(x) begin(x), end(x)
#ifdef CKISEKI
#define safe cerr << __PRETTY_FUNCTION__ << " line " << __LINE__ << " safe\n"
#define debug(a...) debug_(#a, a)
#define orange(a...) orange_(#a, a)
template <typename ...T>
void debug_(const char *s, T ...a) {
    cerr << "\e[1;32m(" << s << ") = (";
    int cnt = sizeof...(T);
    (..., (cerr << a << (--cnt ? ", " : ")\e[0m\n")));
}
template <typename I>
void orange_(const char *s, I L, I R) {
    cerr << "\e[1;32m[ " << s << " ] = [ ";
    for (int f = 0; L != R; L++)
        cerr << (f++ ? ", " : "") << *L;
    cerr << " ]\e[0m\n";
}
#else 
#define safe ((void)0)
#define debug(...) safe
#define orange(...) safe
#endif

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

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int T;
    cin >> T;
    while (T--) {
        int n, m;
        int q;
        cin >> n >> m >> q;
        vector<vector<int>> g(n + 2, vector<int>(m + 2));
        vector<vector<int>> dead(n + 2, vector<int>(m + 2));

        const auto check = [&](int x, int y) {
            return (dead[x + 1][y] || dead[x - 1][y]) && (dead[x][y + 1] || dead[x][y - 1]);
        };

        queue<pair<int,int>> que;
        while (q--) {
            int xx, yy;
            cin >> xx >> yy;
            if (!dead[xx][yy]) {
                dead[xx][yy] = true;
                que.emplace(xx, yy);
            }
            int cnt = 0;

            while (!que.empty()) {
                auto [x, y] = que.front(); que.pop();
                ++cnt;
                for (int k = 0; k < 4; k++) {
                    int nx = x + dx[k];
                    int ny = y + dy[k];
                    if (!dead[nx][ny] && 1 <= nx && nx <= n && 1 <= ny && ny <= m && check(nx, ny)) {
                        dead[nx][ny] = true;
                        que.emplace(nx, ny);
                    }
                }
            }

            cout << cnt << '\n';
        }
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 135ms
memory: 27128kb

input:

10
1 1 2
1 1
1 1
1 2 5
1 2
1 2
1 1
1 2
1 1
1651 1852 69820
938 1459
98 243
1504 554
725 245
601 587
1465 1687
1037 1172
433 1112
173 493
1175 278
302 558
1326 633
375 1043
495 1673
1275 1672
1629 1299
1588 432
507 1754
953 270
1475 1805
1343 1096
798 1633
1124 809
525 1163
1201 1633
1381 578
1489 89...

output:

1
0
1
0
1
0
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
...

result:

ok 576535 lines