情報オリンピック春合宿 2008-day1 Flu

解きました
解法
都市の隣接関係のグラフができれば幅優先探索でO(N)で計算できるので、効率よくグラフを構成する方法を考えればいい。
バケット法を使うとうまくいくらしいが二分探索を2d回行うことでもできた。
計算量はO(d N log N)

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

#define ID second
#define XY first
typedef pair<int, int> P; //((1000x+y, id)
const int MAXN = 100000;
const int MAXM = 100;
const int MAXK = 100;
const int MAXXY = 1000;
int N, M, D, K;
P p[MAXN];
vector<int> G[MAXN];

int dist2(P a, P b){
	int xa, xb, ya, yb, dx, dy;
	xa = a.XY / 1000;
	xb = b.XY / 1000;
	ya = a.XY % 1000;
	yb = b.XY % 1000;
	dx = xa - xb;
	dy = ya - yb;
	return dx*dx + dy*dy;
}
int main(){
	scanf("%d %d %d %d", &N, &M, &D, &K);
	for(int i = 0; i < N; i++){
		int x, y;
		scanf("%d %d", &x, &y);
		p[i] = P(1000 * x + y, i);
	}
	sort(p, p + N);
	for(int i = 0; i < N; i++){
		int id = p[i].ID;
		int x = p[i].XY / 1000;
		int y = p[i].XY % 1000;
		for(int w = x - D; w <= x + D; w++){
			int s, t;
			s = distance(p, lower_bound(p, p+N, P(1000 * w + y - D, 0)));
			t = distance(p, lower_bound(p, p+N, P(1000 * w + y + D + 1, 0)));
			for(int j = s; j < t; j++){
				if(i == j) continue;
				if(dist2(p[i], p[j]) <= D*D){
					G[id].push_back(p[j].ID);
				}
			}
		}
	}

	bool used[N];
	int S[K + 1];
	queue<int> Q;
	fill(used, used + N, false);
	S[0] = 1;
	Q.push(0);
	used[0] = true;
	for(int i = 1; i <= K; i++){
		vector<int> v;
		while(!Q.empty()){
			int id = Q.front(); Q.pop();
			for(int j = 0; j < G[id].size(); j++){
				if(!used[G[id][j]]){
					used[G[id][j]] = true;
					v.push_back(G[id][j]);
				}
			}
		}
		S[i] = v.size();
		for(int j = 0; j < v.size(); j++)
			Q.push(v[j]);
	}
	int ans = 0;
	for(int i = 0; i < M && K-i >= 0; i++){
		ans += S[K-i];
	}
	printf("%d\n", ans);
	return 0;
}