题解：P12506 「ROI 2025 Day2」沼泽里的青蛙

· · 题解

考虑将平面 x,y 轴按 \dfrac r2 分块。观察性质：

  1. 块内所有点相互有边。
  2. 一个点最多和其周围 5\times 5 个块的点连边。

设点数 \ge3 的块为重块。根据性质 1，重块内存在长度 3 奇环。因此重块点和其所在联通块合法。

可以发现不考虑重块点和重块点连边后，剩余边总量是 O(n) 的（根据性质 2，一个点只会有 O(1) 个轻块邻居），这部分直接上扩展域并查集暴力连边找环。

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

#define rep(i,a,b) for(int i = (a);i <= (b);++i)

using ll = long long;

const int N = 1e5 + 5;

int n,B,ans[N],fa[N * 2];
ll m,X[N],Y[N];
map<pair<int,int>,vector<int>> P;

int fnd(int x){ return x == fa[x] ? x : fa[x] = fnd(fa[x]); }

int main(){
    scanf("%d%lld",&n,&m),B = (m + 1) / 2,iota(fa,fa + N * 2,0);
    rep(i,1,n) scanf("%lld%lld",X + i,Y + i),P[make_pair(X[i] / B,Y[i] / B)].push_back(i);
    for(auto&[I,V] : P)
        if(V.size() > 2) for(int k : V) fa[fnd(k)] = fnd(k + n);
        else 
            rep(x,I.first - 2,I.first + 2)
                rep(y,I.second - 2,I.second + 2)
                    if(P.count(make_pair(x,y)))
                        for(int p : V)
                            for(int q : P[make_pair(x,y)])
                                if(p != q && (X[p] - X[q]) * (X[p] - X[q]) + (Y[p] - Y[q]) * (Y[p] - Y[q]) <= m * m)
                                    fa[fnd(p)] = fnd(q + n),fa[fnd(q)] = fnd(p + n);
    rep(i,1,n) putchar((fnd(i) == fnd(i + n)) + '0');
    return 0;
}