BOJ 14632 - 고급 작품

BOJ 14632 - 고급 작품

웰노운? 유형이다.

가장 마지막에 칠해진 것부터 보면서 경로압축으로 모든 칸이 한 번만 봐지게 DSU로 구현하면 된다.

입력을 받는 시간을 제외하면 $O(H \cdot NM)$ 정도로 풀린다.

struct DSU {
   vector<int> p;
   DSU(int n) : p(n, -1) {}
   int gp(int n) {
      if (p[n] < 0) return n;
      return p[n] = gp(p[n]);
   }
   void merge(int a, int b, int to_b = 0) {
      a = gp(a), b = gp(b);
      if (a == b) return;
      if (!to_b && size(a) > size(b)) swap(a, b);
      p[b] += p[a];
      p[a] = b;
   }
   bool is_merged(int a, int b) { return gp(a) == gp(b); }
   int size(int n) { return -p[gp(n)]; }
};

struct Stamp {
   vs s;
   int H, W;
};
void solve() {
   int Y, X;
   cin >> Y >> X;

   vector<DSU> dsu(Y, DSU(X + 1));
   int K;
   cin >> K;
   vector<Stamp> a;
   for (int i = 0; i < K; i++) {
      int H, W;
      cin >> H >> W;
      Stamp stamp;
      stamp.H = H;
      stamp.W = W;
      stamp.s = vs(H);
      fv(stamp.s);
      a.pb(stamp);
   }
   vs ans(Y, string(X, '.'));

   int Q;
   cin >> Q;
   vector<array<int, 3>> qry(Q);
   for (auto &[t, y, x]: qry) cin >> t >> y >> x, t--;

   for (int i = Q - 1; i >= 0; i--) {
      for (int y = qry[i][1]; y < qry[i][1] + a[qry[i][0]].H; y++) {
         int l = qry[i][2], r = qry[i][2] + a[qry[i][0]].W - 1;
         for (int x = l; x <= r;) {
            while (dsu[y].gp(x) != x) x = dsu[y].gp(x);
            if (x > r) break;
            ans[y][x] = a[qry[i][0]].s[y - qry[i][1]][x - l];
            dsu[y].merge(x, x + 1, 1);
            x = dsu[y].gp(x);
         }
      }
   }

   for (int y = 0; y < Y; y++) cout << ans[y] << endl;
}