AOJ 2733: Cube Dividing - SSRS の競プロ日記

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2733

公式解説とは異なる解法で解きました。

問題概要

$A \times B \times C$ 個の同じ大きさの立方体で構成された幅 $A$ 、高さ $B$ 、奥行き $C$ の立方体がある。 $1 \leq i \leq N$ を満たす各 $i$ について、左から $X _ i$ 番目・下から $Y _ i$ 番目・前から $Z _ i$ 番目の立方体を取り除いた。残っている各立方体を頂点とし隣り合う立方体に対応する頂点の間に辺を張った無向グラフの連結成分の個数を求めよ。

解法

以下、 $x, y, z$ 軸をそれぞれ左から右、下から上、前から後ろに取ります。

座標圧縮をして、見る必要のある $x$ 座標を絞ります。具体的には、 $x$ 座標が $0$ 、 $X _ i \ (1 \leq i \leq N)$ 、 $X _ i+1 \ (1 \leq i \leq N, X _ i \lt A - 1)$ の場所のみ考えればよいです。

各 $x$ 座標について、その位置にある取り除いた立方体の $y$ 座標のリストを作り、同様に座標圧縮をします。さらに、各 $y$ 座標について、その位置にある取り除いた立方体の $z$ 座標のリストを作り、ソートして取り除いた立方体の間の直方体に番号を振ります。これにより、立方体が取り除かれた後の立体は $O(N)$ 個の直方体に分割されます。これらの直方体を頂点とし、接している $2$ つの直方体に対応する頂点の間に辺を張った無向グラフを作ることを考えます。

各 $x$ 座標のそれぞれの隣接する $2$ つの $y$ 座標について、 $z$ 座標が変化すると $2$ つの立方体がそれぞれどの直方体に属するか (あるいは、取り除かれていて立体に含まれていないか) がどのように変化するかを調べ、それらが同時に直方体に属している場合、その $2$ つの直方体は接しているので、辺を追加します。

次に、それぞれの隣接する $2$ つの $x$ 座標について、座標圧縮で得た考慮する必要のある $y$ 座標のリストの和集合を求めます。上と同様に、それぞれの $y$ 座標についての $z$ 座標の変化による立方体の所属の変化を調べ、辺を追加します。

グラフが完成したら、そのグラフを連結成分に分解し、連結成分の個数が答えとなります。

計算量は $O(N \log N)$ です。

実装

judge.u-aizu.ac.jp

#include <bits/stdc++.h>
using namespace std;
int main(){
  int A, B, C, N;
  cin >> A >> B >> C >> N;
  vector<int> X(N), Y(N), Z(N);
  for (int i = 0; i < N; i++){
    cin >> X[i] >> Y[i] >> Z[i];
  }
  vector<int> rx;
  rx.push_back(0);
  for (int i = 0; i < N; i++){
    rx.push_back(X[i]);
    if (X[i] < A - 1){
      rx.push_back(X[i] + 1);
    }
  }
  sort(rx.begin(), rx.end());
  rx.erase(unique(rx.begin(), rx.end()), rx.end());
  int A2 = rx.size();
  rx.push_back(A);
  for (int i = 0; i < N; i++){
    X[i] = lower_bound(rx.begin(), rx.end(), X[i]) - rx.begin();
  }
  vector<vector<int>> id(A2);
  for (int i = 0; i < N; i++){
    id[X[i]].push_back(i);
  }
  int V = 0;
  vector<pair<int, int>> E;
  vector<vector<int>> ry(A2);
  vector<int> B2(A2);
  vector<vector<vector<pair<int, int>>>> upd(A2);
  vector<vector<int>> uc(A2);
  for (int i = 0; i < A2; i++){
    ry[i].push_back(0);
    int cnt = id[i].size();
    for (int j = 0; j < cnt; j++){
      ry[i].push_back(Y[id[i][j]]);
      if (Y[id[i][j]] < B - 1){
        ry[i].push_back(Y[id[i][j]] + 1);
      }
    }
    sort(ry[i].begin(), ry[i].end());
    ry[i].erase(unique(ry[i].begin(), ry[i].end()), ry[i].end());
    B2[i] = ry[i].size();
    vector<vector<int>> id2(B2[i]);
    for (int j = 0; j < cnt; j++){
      int Y2 = lower_bound(ry[i].begin(), ry[i].end(), Y[id[i][j]]) - ry[i].begin();
      id2[Y2].push_back(id[i][j]);
    }
    upd[i].resize(B2[i]);
    for (int j = 0; j < B2[i]; j++){
      int cnt2 = id2[j].size();
      for (int k = 0; k < cnt2; k++){
        upd[i][j].push_back(make_pair(Z[id2[j][k]], -1));
      }
      vector<int> rz;
      rz.push_back(-1);
      rz.push_back(C);
      for (int k = 0; k < cnt2; k++){
        rz.push_back(Z[id2[j][k]]);
      }
      sort(rz.begin(), rz.end());
      int cnt3 = rz.size();
      for (int k = 0; k < cnt3 - 1; k++){
        if (rz[k + 1] - rz[k] > 1){
          upd[i][j].push_back(make_pair(rz[k] + 1, V));
          V++;
        }
      }
    }
    uc[i].resize(B2[i]);
    for (int j = 0; j < B2[i]; j++){
      uc[i][j] = upd[i][j].size();
    }
    for (int j = 0; j < B2[i] - 1; j++){
      vector<tuple<int, int, int>> upd2;
      for (int k = 0; k < 2; k++){
        for (int l = 0; l < uc[i][j + k]; l++){
          upd2.push_back(make_tuple(upd[i][j + k][l].first, k, upd[i][j + k][l].second));
        }
      }
      sort(upd2.begin(), upd2.end());
      int cnt2 = upd2.size();
      vector<int> c = {-1, -1};
      for (int k = 0; k < cnt2; k++){
        int t = get<0>(upd2[k]);
        int h = get<1>(upd2[k]);
        int v = get<2>(upd2[k]);
        c[h] = v;
        bool ok = true;
        if (k < cnt2 - 1){
          if (get<0>(upd2[k + 1]) == t){
            ok = false;
          }
        }
        if (ok){
          if (c[0] != -1 && c[1] != -1){
            E.push_back(make_pair(c[0], c[1]));
          }
        }
      }
    }
  }
  for (int i = 0; i < A2 - 1; i++){
    vector<int> ry2;
    for (int j = i; j <= i + 1; j++){
      for (int k = 0; k < B2[j]; k++){
        ry2.push_back(ry[j][k]);
      }
    }
    sort(ry2.begin(), ry2.end());
    ry2.erase(unique(ry2.begin(), ry2.end()), ry2.end());
    int cnt = ry2.size();
    for (int j = 0; j < cnt; j++){
      vector<int> yp(2);
      for (int k = 0; k < 2; k++){
        yp[k] = upper_bound(ry[i + k].begin(), ry[i + k].end(), ry2[j]) - ry[i + k].begin() - 1;
      }
      vector<tuple<int, int, int>> upd2;
      for (int k = 0; k < 2; k++){
        for (int l = 0; l < uc[i + k][yp[k]]; l++){
          upd2.push_back(make_tuple(upd[i + k][yp[k]][l].first, k, upd[i + k][yp[k]][l].second));
        }
      }
      sort(upd2.begin(), upd2.end());
      int cnt2 = upd2.size();
      vector<int> c = {-1, -1};
      for (int k = 0; k < cnt2; k++){
        int t = get<0>(upd2[k]);
        int h = get<1>(upd2[k]);
        int v = get<2>(upd2[k]);
        c[h] = v;
        bool ok = true;
        if (k < cnt2 - 1){
          if (get<0>(upd2[k + 1]) == t){
            ok = false;
          }
        }
        if (ok){
          if (c[0] != -1 && c[1] != -1){
            E.push_back(make_pair(c[0], c[1]));
          }
        }
      }
    }
  }
  int M = E.size();
  vector<vector<int>> E2(V);
  for (int i = 0; i < M; i++){
    int v = E[i].first;
    int w = E[i].second;
    E2[v].push_back(w);
    E2[w].push_back(v);
  }
  int ans = 0;
  vector<bool> used(V, false);
  for (int i = 0; i < V; i++){
    if (!used[i]){
      used[i] = true;
      ans++;
      queue<int> Q;
      Q.push(i);
      while (!Q.empty()){
        int v = Q.front();
        Q.pop();
        for (int w : E2[v]){
          if (!used[w]){
            used[w] = true;
            Q.push(w);
          }
        }
      }
    }
  }
  cout << ans << endl;
}