QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#513723#9170. Cycle Gameucup-team004#WA 0ms3768kbC++203.5kb2024-08-10 19:16:532024-08-10 19:16:53

Judging History

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

  • [2024-08-10 19:16:53]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3768kb
  • [2024-08-10 19:16:53]
  • 提交

answer

#include <bits/stdc++.h>

using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;

constexpr int V = 300001;

int f[V], siz[V];
int find(int x) {
    while (x != f[x]) {
        x = f[x];
    }
    return x;
}

std::vector<int> his;

bool merge(int a, int b) {
    a = find(a);
    b = find(b);
    if (a == b) {
        return false;
    }
    if (siz[a] < siz[b]) {
        std::swap(a, b);
    }
    his.push_back(b);
    f[b] = a;
    siz[a] += siz[b];
    return true;
}

void revert(int t) {
    while (his.size() > t) {
        int b = his.back();
        his.pop_back();
        int a = f[b];
        siz[a] -= siz[b];
        f[b] = b;
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n, m, k;
    std::cin >> n >> m >> k;
    
    std::vector<int> r(k), c(k);
    for (int i = 0; i < k; i++) {
        std::cin >> r[i] >> c[i];
        r[i]--;
        c[i]--;
    }
    
    const int N = n * m;
    std::vector<int> col(N);
    
    std::iota(f, f + N + 1, 0);
    std::fill(siz, siz + N + 1, 1);
    
    int M = 1;
    while (M < k) {
        M *= 2;
    }
    M *= 2;
    
    std::vector<std::vector<int>> vec(M);
    auto add = [&](auto self, int p, int l, int r, int x, int y, int cell) {
        if (l >= y || r <= x) {
            return;
        }
        if (l >= x && r <= y) {
            vec[p].push_back(cell);
            return;
        }
        int m = (l + r) / 2;
        self(self, 2 * p, l, m, x, y, cell);
        self(self, 2 * p + 1, m, r, x, y, cell);
    };
    
    auto valid = [&](int x, int y) {
        return 0 <= x && x < n && 0 <= y && y < m;
    };
    
    std::vector<int> lst(N);
    for (int i = 0; i < k; i++) {
        int cell = r[i] * m + c[i];
        add(add, 1, 0, k, lst[cell], i, cell);
        lst[cell] = i + 1;
    }
    for (int cell = 0; cell < N; cell++) {
        add(add, 1, 0, k, lst[cell], k, cell);
    }
    
    int comp = 1;
    std::vector<bool> ans(k);
    std::vector<bool> vis(N);
    auto dfs = [&](auto self, int p, int L, int R) -> void {
        const int t = his.size();
        const int oldcomp = comp;
        for (auto cell : vec[p]) {
            if (col[cell] == 1) {
                continue;
            }
            int x = cell / m;
            int y = cell % m;
            comp++;
            vis[cell] = true;
            for (int dx = -1; dx <= 1; dx++) {
                for (int dy = -1; dy <= 1; dy++) {
                    int nx = x + dx;
                    int ny = y + dy;
                    int v = nx * m + ny;
                    if (valid(nx, ny) && vis[v]) {
                        comp -= merge(cell, v);
                    }
                }
            }
            if (x == 0 || x == n - 1 || y == 0 || y == m - 1) {
                comp -= merge(cell, N);
            }
        }
        if (R - L == 1) {
            int cell = r[L] * m + c[L];
            assert(col[cell] == 0);
            if (comp == 1) {
                col[cell] = 1;
                ans[L] = true;
            }
        } else {
            int m = (L + R) / 2;
            self(self, 2 * p, L, m);
            self(self, 2 * p + 1, m, R);
        }
        revert(t);
        comp = oldcomp;
        for (auto cell : vec[p]) {
            vis[cell] = false;
        }
    };
    dfs(dfs, 1, 0, k);
    
    for (int i = 0; i < k; i++) {
        std::cout << ans[i];
    }
    std::cout << "\n";
    
    return 0;
}

详细

Test #1:

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

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: 3620kb

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: 3628kb

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: 0ms
memory: 3568kb

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: 3628kb

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: 3560kb

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: 3620kb

input:

1 4 1
1 2

output:

1

result:

ok "1"

Test #8:

score: -100
Wrong Answer
time: 0ms
memory: 3768kb

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:

1111111111111111111111111111111111111111111110011111101010001101111

result:

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