Code snippets

Appearance

ICPC模擬国内予選2020-B: 爆発の連鎖 ​

問題 ​

解説 ​

任意の2つの爆弾について, 誘爆するかどうかを判定し誘爆するならば辺を張る.

答えはB番目 (1-index) の爆弾の連結成分のサイズとなる.

以下の2つの条件を調べて満たすならば誘爆すると判定すれば良い.

  • x座標が等しくy座標の差がD以下
  • y座標が等しくx座標の差がD以下

計算量は O(N2α(N))

実装例 ​

C++ ​

cpp
#include <iostream>
#include <vector>

struct UnionFind {
  std::vector<int> parent_or_size;
  int cnt;

  UnionFind(int n) : parent_or_size(n, -1), cnt(n) {}

  void unite(int x, int y) {
    x = find_root(x);
    y = find_root(y);
    if (x == y) {
      return;
    }
    if (-parent_or_size[x] < -parent_or_size[y]) {
      std::swap(x, y);
    }
    parent_or_size[x] += parent_or_size[y];
    parent_or_size[y] = x;
    cnt--;
  }
  bool is_same_root(int x, int y) { return find_root(x) == find_root(y); }
  int find_root(int x) {
    if (parent_or_size[x] < 0) {
      return x;
    }
    return parent_or_size[x] = find_root(parent_or_size[x]);
  }
  int size(int x) { return -parent_or_size[find_root(x)]; }
};

int main() {
  int W, H, N, D, B;

  while (true) {
    std::cin >> W >> H >> N >> D >> B;
    if (W == 0 && H == 0 && N == 0 && D == 0 && B == 0) {
      break;
    }

    std::vector<int> x(N), y(N);
    for (int i = 0; i < N; i++) {
      std::cin >> x[i] >> y[i];
    }

    UnionFind uf_tree(N);
    for (int i = 0; i < N; i++) {
      for (int j = 0; j < N; j++) {
        if ((x[i] == x[j] && std::abs(y[i] - y[j]) <= D) ||
            (y[i] == y[j] && std::abs(x[i] - x[j]) <= D)) {
          uf_tree.unite(i, j);
        }
      }
    }
    std::cout << uf_tree.size(B - 1) << "\n";
  }
  return 0;
}

Python ​

python
#!/usr/bin/env python3


class UnionFind:
    def __init__(self, n):
        self.parent_or_size = [-1 for _ in range(n)]
        self.cnt = n

    def unite(self, x, y):
        x, y = self.find_root(x), self.find_root(y)
        if x == y:
            return
        if -self.parent_or_size[x] < -self.parent_or_size[y]:
            x, y = y, x
        self.parent_or_size[x] += self.parent_or_size[y]
        self.parent_or_size[y] = x
        self.cnt -= 1

    def is_same_root(self, x, y):
        return self.find_root(x) == self.find_root(y)

    def find_root(self, x):
        if self.parent_or_size[x] < 0:
            return x
        self.parent_or_size[x] = self.find_root(self.parent_or_size[x])
        return self.parent_or_size[x]

    def size(self, x):
        return -self.parent_or_size[self.find_root(x)]


while True:
    W, H, N, D, B = map(int, input().split())

    if W == 0 and H == 0 and N == 0 and D == 0 and B == 00:
        break

    xy = [[int(x) for x in input().split()] for _ in range(N)]

    uf_tree = UnionFind(N)
    for i in range(N):
        for j in range(N):
            xi, yi = xy[i]
            xj, yj = xy[j]

            if xi == xj and abs(yi - yj) <= D:
                uf_tree.unite(i, j)
            if yi == yj and abs(xi - xj) <= D:
                uf_tree.unite(i, j)

    print(uf_tree.size(B - 1))