BOJ 25596 - 마트료시카 박스 II

BOJ 25596 - 마트료시카 박스 II

만약 가진 상자의 수가 $M$ 보다 많다면 $M-1$ 개는 기존에 가진걸로 채우고 마지막 하나만 상자를 새롭게 추가해 남은 자식들을 그 상자들에게 모두 몰아주는 식으로 재귀적으로 호출하면 된다.

void solve() {
   int n, m, k;
   cin >> n >> m >> k;
   vvi e1(n);
   auto fail = [&]() {
      cout << 0;
      exit(0);
   };
   int need = 0;
   for (int i = 0; i < n; i++) {
      int cnt, x, par = i;
      cin >> cnt;
      vi child(cnt);
      fv(child);
      for (int &j: child)j--;
      function<void(int, vi)> resolve = [&](int cur, vi child) -> void {
         if (sz(child) <= m) {
            for (int j: child) e1[cur].pb(j);
            return;
         }
         int group = (sz(child) + m - 1) / m;
         int remain = m;
         for (int i = 0; i < m - 1; i++) {
            e1[cur].pb(child.back());
            child.pop_back();
         }
         int new_box = sz(e1);
         e1[cur].pb(new_box);
         e1.emplace_back();
         resolve(new_box, child);
      };

      if (m == 1 && sz(child) > 1) {
         fail();
      }

      resolve(i, child);
   }
   
   int added = sz(e1) - n;
   if (sz(e1) - n > k) fail();
   cout << 1 << endl;
   cout << sz(e1) - n << endl;
   for (int i = 0; i < sz(e1); i++) {
      cout << sz(e1[i]) << ' ';
      assert(sz(e1[i]) <= m);
      for (int j: e1[i]) cout << j + 1 << ' ';
      cout << endl;
   }
}