线段树分治 100pts 但是 hack 数据 TLE

P5787 二分图 /【模板】线段树分治

看这一段。 ```cpp for(auto [x, y] : g[k]) { int p = find(x), q = find(y); res &= (p != q); // cout << "q" << x << ' ' << y << ':' << p << ' ' << q << endl; merge(p, find(y + n)); merge(find(x + n), q); } ``` 在 `p==q` 时(`res` 已经为 0,其实完全可以直接输出一些 `No` 然后 `return`),这个时候下面那两句合并经过手玩发现会产生环然后 `find` 炸了,所以这样写就行。 ```cpp for (auto [x, y] : g[k]) { int p = find(x), q = find(y); res &= (p != q); // cout << "q" << x << ' ' << y << ':' << p << ' ' << q << endl; if (res) { merge(p, find(y + n)); merge(find(x + n), q); } } ``` 当然我更推荐直接输出然后 `return`。
by fangzichang @ 2024-01-04 16:01:02


@[fangzichang](/user/678087) 您没 @ 上我所以刚刚才看到。十分感谢,我自己调怎么也想不到原来是 find 炸了。
by _NTT_ @ 2024-01-06 08:52:03


|