BOJ 20156 - 기왕 이렇게 된 거 암기왕이 되어라

BOJ 20156 - 기왕 이렇게 된 거 암기왕이 되어라

문제를 읽고 Offline Query + DSU 임은 자명해보였으나 엣지 케이스를 고려하지 못했다.

상당히 입력이 자유롭게 들어와서 입력도 잘 처리해줘야 하는 문제이고 엣지 케이스도 있다.

$x$ 가 부모가 있다고 할 때 $t=2$ 에서 제거가 되었다면 $t=5$ 에서 $x$ 가 다시 제거되어도 그건 무시해줘야 한다.

왜냐면 이미 $t=2$ 에서 부모가 제거가 되어있기 때문에 $t=5$ 에서는 부모가 없는 분리된 트리의 루트인 상태이기 때문이다.

또한 처음에 부모-자식 관계가 끝까지 끊어지지 않는다면 처음에 DSU에서 모두 이어주고 시작해야 함을 유의하자.

나머지는 어렵지 않다. 쿼리를 $t$ 를 내림차순으로 정렬하고, 하나하나 보며 분리의 역은 merge 이므로 DSU에서 현재 쿼리의 시점보다 뒤인 것들은 모두 merge 시켜주고 DSU에서 이어져있는지를 판단하면 된다.

void solve() {  
   int n, m, k;  
   cin >> n >> m >> k;  
   DSU dsu(n);  
   vi par(n);  
   for (int i = 0; i < n; i++) {  
      cin >> par[i];  
      if (par[i] != -1) par[i]--;  
      assert(i != par[i]);  
   }  
   vi disconnect(m + 1), removed(n);  
   for (int i = 0; i < m; i++) {  
      int d;  
      cin >> d;  
      d--;  
      if (par[d] != -1 && removed[d] == 0) {  
         removed[d] = 1;  
         disconnect[i + 1] = d;  
      } else {  
         disconnect[i + 1] = -1;  
      }  
   }  
   for (int i = 0; i < n; i++) {  
      if (!removed[i] && par[i] != -1) {  
         debug(i, par[i]);  
         dsu.merge(par[i], i);  
      }  
   }  
   debug(disconnect);  
  
   vi ans(k);  
   vector<array<int, 4>> qry(k);  
   for (int i = 0; i < k; i++) {  
      cin >> qry[i][0] >> qry[i][1] >> qry[i][2];  
      qry[i][3] = i;  
      qry[i][1]--;  
      qry[i][2]--;  
   }  
   sort(all(qry), [&](auto &a, auto &b) {  
      return a[0] > b[0];  
   });  
   // 1 2 3  
   //   d  qry  
   for (int i = 0, j = m; i < k; i++) {  
      while (j >= 1 && j > qry[i][0]) {  
         int x = disconnect[j];  
         if (x != -1) {  
            dsu.merge(par[x], x);  
         }  
         j--;  
      }  
      if (dsu.is_merged(qry[i][1], qry[i][2])) ans[qry[i][3]] = 1;  
   }  
   for (int i = 0; i < k; i++) {  
      if (ans[i]) cout << "Same Same;\n";  
      else cout << "No;\n";  
   }  
}