第七个点RE以及部分题解存在的问题

P3806 【模板】点分治 1

TJUHuangTao @ 2024-08-15 10:34:39

一直RE在第七个点,对比了之前的代码,发现几乎没有区别,然后发现是数组越界,就加了很多assert终于发现了问题。

第七个样例里面,路径长度可能是超过 10^7的,然后用的桶,就可能把这个越界的长度存起来,后面清空的时候就越界,所以需要在用队列储存需要清空的数值时判断一下,超过 10^7 的就不存了,然后就能过了。

不过奇怪的是,看了有的题解也有这样的问题,不过交上去似乎还是过了。

void calc(int u) {
    for (auto [v, w] : G[u]) {
        if (del[v])
            continue;
        tmp[0] = 0;
        dis[v] = w;
        get_dis(v, u);
        for (int i = tmp[0]; i; i--) {
            for (int j = 1; j <= m; j++) {
                if (query[j] >= tmp[i])
                    ans[j] |= lens[query[j] - tmp[i]];
            }
        }
        for (int i = tmp[0]; i; i--) {
            if (tmp[i] < maxlen)  // 这里加个判断
                q.push(tmp[i]), lens[tmp[i]] = 1;
        }
    }
    while (!q.empty())
        lens[q.front()] = 0, q.pop();
}

|