Wireless network (preprocessing + concurrent search)

Topic link

https://www.acwing.com/problem/content/4269/

Ideas

because n For the range of 1k, Then we can put every point in advance d All points in the range are stored , This is an edge that is not clear whether it can be connected , Let's have another one $vis[i]$ Record the current number i Whether the computer is turned on . As for the relationship between these computers, we can maintain computers in the same set by merging and searching sets , We now have two operations ：

• 'O’ operation ： take p Computer on
• 'S’ operation ： Inquire about p and q Whether in a collection

As mentioned earlier, we maintain this data relationship by merging and searching sets , For the first operation , We will p All around the computer Turn on the computer Merge (merge operation ) And put the current computer Mark as power on , For the second operation, we directly query p Computer and q Whether the computer is in the same set

Code

#include<bits/stdc++.h>
using namespace std;
//---------------- Custom part ----------------
#define ll long long
#define mod 1000000007
#define endl "\n"
#define PII pair<int,int>
#define INF 0x3f3f3f3f

int dx[4] = {
    -1, 0, 1, 0}, dy[4] = {
    0, 1, 0, -1};

ll ksm(ll a,ll b) {
    
	ll ans = 1;
	for(;b;b>>=1LL) {
    
		if(b & 1) ans = ans * a % mod;
		a = a * a % mod;
	}
	return ans;
}

ll lowbit(ll x){
    return -x & x;}

const int N = 1e3+10;
//---------------- Custom part ----------------
ll t,n,d,m,fa[N];

struct Point{
    
	ll x,y;
};
vector<Point> V;
vector<int> E[N];
bool vis[N];

ll find(ll x){
    
	ll t = x;
	while(t != fa[t]) t = fa[t];
	while(x != fa[x]){
    
		ll temp = fa[x];
		fa[x] = t;
		x = temp;
	}
	return x;
}

bool is_in(Point a,Point b){
    
	ll x = (a.x - b.x),y = (a.y - b.y);
	ll len = x * x + y * y;
	return len <= d * d;
}

void init(){
    
	ll x,y;
	V.clear();
	V.push_back({
    0,0});
	for(int i = 1;i <= n; ++i) {
    
		vis[i] = false;
		fa[i] = i;
		cin>>x>>y;
		V.push_back({
    x,y});
		E[i].clear();
	}
	for(int i = 1;i <= n; ++i) {
    
		for(int j = 1;j <= n; ++j) {
    
			if(i == j) continue;
			if(is_in(V[i],V[j])) 
				E[i].push_back(j);
		}
	}
}

void slove(){
    
	init();
	char op;
	while(cin>>op) {
    
		ll u,v,k;
		if(op == 'O'){
    
			cin>>u;
			k = find(u);
			for(int i = 0,l = E[u].size();i < l; ++i) {
    
				if(!vis[E[u][i]]) continue;
				v = find(E[u][i]);
				if(k != v)	fa[v] = k;
			}
			vis[u] = true;
		}
		else{
    
			cin>>u>>v;
			u = find(u),v = find(v);
			if(u == v)
				cout<<"SUCCESS"<<endl;
			else
				cout<<"FAIL"<<endl;
		}
	}
}

int main()
{
    
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	while(cin>>n>>d){
    
		slove();
	}
	
	return 0;
}