QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#549628#9170. Cycle Gameucup-team3519#WA 1ms3808kbC++232.1kb2024-09-06 19:06:372024-09-06 19:06:38

Judging History

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

  • [2024-09-06 19:06:38]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3808kb
  • [2024-09-06 19:06:37]
  • 提交

answer

#include <bits/stdc++.h>

struct DSU {
    std::vector<int> fa;
    explicit DSU(int n) : fa(n) {
        std::iota(fa.begin(), fa.end(), 0);
    }
    int find(int x) {
        return fa[x] == x ? x : fa[x] = find(fa[x]);
    }
    bool merge(int x, int y) {
        x = find(x), y = find(y);
        if (x == y) {
            return false;
        }
        fa[x] = y;
        return true;
    }
};

int main() {
    int n, m, k;
    std::cin >> n >> m >> k;

    std::vector<std::pair<int, int>> p(k);
    for (auto &[x, y] : p) {
        std::cin >> x >> y;
        --x, --y;
    }

    std::vector<uint8_t> ans(k);

    DSU dsu(n * m + 1);
    const int t = n * m;

    auto coord = [&](int x, int y) {
        if (x < 0 || x >= n || y < 0 || y >= m) {
            return t;
        }
        return x * m + y;
    };

    std::vector<uint8_t> vis(n * m + 1, true);
    for (auto [r, c] : p) {
        vis[coord(r, c)] = false;
    }

    for (int r = 0; r < n; ++r) {
        for (int c = 0; c < m; ++c) {
            if (!vis[coord(r, c)]) {
                continue;
            }
            for (int dx = -1; dx <= 1; ++dx) {
                for (int dy = -1; dy <= 1; ++dy) {
                    if (dx == 0 && dy == 0) {
                        continue;
                    }
                    int x = r + dx, y = c + dy;
                    if (vis[coord(x, y)]) {
                        dsu.merge(coord(x, y), coord(r, c));
                    }
                }
            }
        }
    }
    
    for (int i = k - 1; i >= 0; --i) {
        auto [r, c] = p[i];

        vis[coord(r, c)] = true;
        int mc = 0;
        for (int dx = -1; dx <= 1; ++dx) {
            for (int dy = -1; dy <= 1; ++dy) {
                if (dx == 0 && dy == 0) {
                    continue;
                }
                int x = r + dx, y = c + dy;
                if (vis[coord(x, y)]) {
                    mc += dsu.merge(coord(x, y), coord(r, c));
                }
            }
        }

        ans[i] = (mc <= 1);
    }

    for (int i : ans) {
        std::cout << i;
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3776kb

input:

4 3 7
2 1
2 2
2 3
3 1
3 2
4 1
4 2

output:

1111111

result:

ok "1111111"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3644kb

input:

3 3 8
1 1
1 2
1 3
2 3
3 3
3 2
3 1
2 1

output:

11111110

result:

ok "11111110"

Test #3:

score: 0
Accepted
time: 0ms
memory: 3544kb

input:

10 10 7
9 1
6 6
3 8
8 7
5 10
1 7
1 2

output:

1111111

result:

ok "1111111"

Test #4:

score: 0
Accepted
time: 1ms
memory: 3616kb

input:

9 10 50
1 9
1 6
2 3
3 1
7 4
9 4
1 3
2 5
9 2
7 9
5 6
8 10
9 5
5 5
4 10
9 7
5 9
3 2
4 5
1 1
4 7
3 6
2 8
4 3
8 6
5 10
4 8
5 4
7 2
9 6
4 2
7 8
5 2
3 5
9 1
6 1
1 5
9 9
5 8
6 3
8 8
8 4
7 7
7 1
3 7
2 2
3 10
6 9
8 3
7 6

output:

11111111111111111111111111111111111111111111111111

result:

ok "11111111111111111111111111111111111111111111111111"

Test #5:

score: 0
Accepted
time: 0ms
memory: 3496kb

input:

3 5 11
1 5
2 4
1 2
1 3
3 3
3 1
3 4
2 3
1 4
2 1
2 5

output:

11111111111

result:

ok "11111111111"

Test #6:

score: 0
Accepted
time: 0ms
memory: 3648kb

input:

7 9 12
7 3
2 3
6 2
2 2
4 2
2 8
5 7
4 4
6 8
2 7
7 2
1 9

output:

111111111111

result:

ok "111111111111"

Test #7:

score: 0
Accepted
time: 0ms
memory: 3784kb

input:

1 4 1
1 2

output:

1

result:

ok "1"

Test #8:

score: -100
Wrong Answer
time: 1ms
memory: 3808kb

input:

9 8 67
5 5
8 3
9 5
7 4
5 1
9 3
4 2
2 5
1 7
7 8
7 2
8 5
6 1
8 8
4 4
5 4
1 5
3 4
6 7
2 3
3 7
5 7
2 4
2 7
1 3
7 3
2 8
6 6
6 2
6 3
7 5
9 6
7 6
3 6
1 1
6 4
3 1
5 3
8 7
2 1
4 1
8 4
8 6
3 5
5 8
1 6
1 2
4 6
9 4
1 4
3 3
4 8
8 1
4 7
9 8
3 8
6 5
6 8
3 2
2 2
7 1
9 2
4 3
1 8
4 5
8 2
7 7

output:

1111111111111111111111111111111111111111111110011111101110011111111

result:

wrong answer 1st words differ - expected: '111111111111111111111111111111...1111111110010101101000101101101', found: '111111111111111111111111111111...1111111110011111101110011111111'