自动搬运

查看原文

来自洛谷，原作者为

	xfrvq **

搬运于2025-08-24 23:16:04，当前版本为作者最后更新于2025-06-23 14:21:43，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

考虑将平面 $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;
}