情報オリンピック春合宿 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; }