Http://usaco.org/index.php?page=viewproblem2&cpid=996

Debugging Help
#1

Problem Info

Cave Paintings, USACO

My Work

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

const int maxn = 1000;
const int maxsz = maxn * maxn;
const int MOD = 1e9 + 7;

int add(int a, int b) {
    int x = a + b;
    if (x > MOD)
        return x - MOD;
    return x;
}

int mult(int a, int b) {
    return (1ll * a * b) % MOD;
}

int n, m;
int grid[maxsz];

int root[maxsz];
int top[maxsz];
vector<int> chld[maxsz];
int dp[maxsz];

int find(int nd) {
    if (nd == root[nd])
        return nd;
    return root[nd] = find(root[nd]);
}

void unite(int a, int b) {
    a = find(a), b = find(b);

    if (a == b)
        return;

    root[b] = a;
}

#define f(a, b) ((a) * m + (b))

void combine(int nd) {
    dp[nd] = 1;

    for (auto i : chld[nd])
        dp[nd] = mult(dp[nd], i);

    dp[nd] = add(dp[nd], 1);
}

int main() {
    cin.tie(nullptr); ios::sync_with_stdio(false);

    // freopen("main.in", "r", stdin);

    freopen("cave.in", "r", stdin);
    freopen("cave.out", "w", stdout);

    cin >> n >> m;

    for (int i = 0; i < n * m; i++)
        root[i] = i, top[i] = -1, dp[i] = 1;

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) {
            char c; cin >> c;
            grid[f(i, j)] = c == '.';
        }

    for (int i = n - 2; i >= 1; i--) {
        for (int j = 1; j < m - 1; j++)
            if (grid[f(i, j)] && grid[f(i, j - 1)])
                unite(f(i, j), f(i, j - 1));

        for (int j = 1; j < m - 1; j++) {
            if (!grid[f(i, j)])
                continue;

            if (grid[f(i, j - 1)])
                unite(f(i, j), f(i, j - 1));

            if (grid[f(i + 1, j)]) {
                if (top[find(f(i + 1, j))] == -1) {
                    top[find(f(i + 1, j))] = find(f(i, j));
                    chld[find(f(i, j))].push_back(dp[find(f(i + 1, j))]);
                } else {
                    unite(top[find(f(i + 1, j))], find(f(i, j)));
                }
            }
        }

        for (int j = 1; j < m - 1; j++) {
            if (!grid[f(i, j)])
                continue;

            if (f(i, j) != root[f(i, j)])
                continue;

            combine(f(i, j));
        }
    }

    for (int i = 1; i < n - 1; i++)
        for (int j = 1; j < m - 1; j++)
            if (grid[f(i, j)] && grid[f(i + 1, j)])
                unite(f(i, j), f(i + 1, j));

    int ans = 1;

    for (int i = 1; i < n - 1; i++)
        for (int j = 1; j < m - 1; j++)
            if (grid[f(i, j)] && root[f(i, j)] == f(i, j))
                ans = mult(ans, dp[f(i, j)]);

    cout << ans << '\n';
}

My algorithm is very similar to the solution. At each layer, I use union-find to merge all the nodes which are connected using lower cells. I have written my union find in a way such that the root node will always be the leftmost node in the layer. I then multiply all the children node’s dp values, then add 1, like the solution.

Since it is a forest, in the end, I merge all the nodes in the same tree, and then multiply the dp values of each tree together to get the final answer. It works for all the smaller test cases (1-5) and the last test case (15), but not any in between.

What I’ve Tried

I tried downloading the test data, but my code is only failing cases from test case 6 and onward, where n, m are 1000. I’ve looked over my code multiple times, and rewritten it from scratch, but can’t find the error. Can someone help me find where I am going wrong?

#2

\quad