結果

問題 No.2987 Colorful University of Tree
ユーザー Xiaohuba
提出日時 2025-05-25 01:17:23
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,081 ms / 5,000 ms
コード長 5,829 bytes
コンパイル時間 3,035 ms
コンパイル使用メモリ 231,196 KB
実行使用メモリ 98,900 KB
最終ジャッジ日時 2025-05-25 01:17:52
合計ジャッジ時間 27,012 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 42
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;

// #define LOCK_GETCHAR
// #define USE_INT_128
// #undef DEBUG

#ifdef DEBUG
#include <moeebius/debug.hpp>
#else
#define debug(...) (void(0))
#define Debug(...) (void(0))
#endif

#define ENABLE_IF_INT , enable_if_t<_is_integer<T>, int> = 0
template <class T> constexpr bool _is_integer = numeric_limits<T>::is_integer;
template <> constexpr bool _is_integer<bool> = false;
template <> constexpr bool _is_integer<char> = false;
#ifdef USE_INT_128
template <> constexpr bool _is_integer<__int128> = true;
template <> constexpr bool _is_integer<__uint128_t> = true;
#endif

#if !defined(_WIN32) && !defined(__CYGWIN__) && !defined(LOCK_GETCHAR)
#define getchar getchar_unlocked
#endif

#define il inline
#define mkp make_pair
#define fi first
#define se second
#define ssz(x) (signed((x).size()))
#define beg2ed(x) (x).begin(), (x).end()
#define _loop_i_t(j, k) make_signed_t<decltype((j) - (k))>
#define For(i, j, k) for (_loop_i_t(j, k) i = (j); i <= (k); ++i)
#define ForDown(i, j, k) for (_loop_i_t(j, k) i = (j); i >= decltype(i)(k); --i)
#define eb emplace_back
#ifndef ONLINE_JUDGE
#define FileIO(filename)                                                       \
  freopen(filename ".in", "r", stdin);                                         \
  freopen(filename ".out", "w", stdout)
#else
#define FileIO(filename) void(0)
#endif

using ll = long long;
using uint = unsigned int;
using ull = unsigned long long;
using db = double;
using ldb = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#ifdef USE_INT_128
using lll = __int128_t;
using ulll = __uint128_t;
#endif

// clang-format off
constexpr il ll qpow(ll x, ull y, ll mod){ ll ans = 1; x %= mod; while (y) { if (y & 1) (ans *= x) %= mod; (x *= x) %= mod; y >>= 1; } return ans; }
template<typename T> constexpr il void cmin(T & x, const T &y){ x = min(x, y); }
template<typename T> constexpr il void cmax(T & x, const T &y){ x = max(x, y); }
template<typename T ENABLE_IF_INT> il void read(T &x){ x = 0; int f = 1; int c = getchar(); while (!isdigit(c)) { if (c == '-') f = -1; c = getchar(); } while (isdigit(c)) { x = x * 10 + (c - '0'); c = getchar(); } x *= f; }
template<typename T, typename ... Args> il void read(T &x, Args &... y){ read(x), read(y...); }
// clang-format on

// File head end

namespace {
constexpr ll MAXN = 2e5 + 5;
int Tc, n, val[MAXN], id[MAXN], sum[MAXN];
pii E[MAXN];
vector<int> T[MAXN];
vector<pii> G[MAXN], G2[MAXN];
mt19937 rnd(12345);
map<pii, int> col;
map<int, pii> mp[MAXN];
bool is_todo[MAXN];
void solve() {
  read(n);
  col.clear();
  For(i, 0, n) mp[i].clear(), is_todo[i] = 0, G[i].clear(), G2[i].clear(), T[i].clear(), val[i] = id[i] = sum[i] = 0, E[i] = {};
  int cnt = 0, ans = 0;
  For(i, 1, n) {
    int len;
    read(len), T[i].resize(len), cnt += (len & 1);
    cmax(ans, len);
    for (int &e : T[i])
      read(e), (!E[e].fi ? E[e].fi : E[e].se) = i;
  }
  cmax(ans, (int)ceil(sqrt(2 * (n - 1))));
  if ((ans & 1) && ll(ans) * ans - 2 * (n - 1) + cnt < ans)
    ans++;
  cout << ans << '\n';
  iota(id + 1, id + 1 + n, 1);
  sort(id + 1, id + 1 + n, [&](int x, int y) { return ssz(T[x]) < ssz(T[y]); });
  int p = 1;
  cnt = 0;
  while (ssz(T[id[p + 1]]) == 1)
    p++;
  for (int i = n, j = p + 1; i >= j; i--) {
    ++cnt;
    sum[cnt] = ssz(T[id[i]]), val[id[i]] = cnt;
    while (j < i && sum[cnt] + ssz(T[id[j]]) <= ans)
      val[id[j]] = cnt, sum[cnt] += ssz(T[id[j++]]);
    assert(sum[cnt] <= ans);
  }
  int q = 1;
  For(i, 1, p) {
    while (sum[q] == ans)
      q++;
    assert(sum[q] < ans);
    sum[q]++, val[id[i]] = q;
    assert(sum[q] <= ans);
    assert(ssz(T[id[i]]) == 1);
  }
  // cerr << p << ' ' << cnt << ' ' << q << ' ' << ans << '\n';
  cmax(cnt, q);
  assert(cnt <= ans);
  vector<int> U(ans);
  iota(beg2ed(U), 1);
  For(i, 1, n) for (int e : T[i]) G[val[i]].eb(e, i), G2[e].eb(val[i], i);
  For(i, 1, ans) {
    vector<int> tmp;
    assert(ssz(G[i]) <= ans);
    for (auto [e, x] : G[i]) {
      int j = rnd() % ssz(U);
      swap(U[j], U.back());
      assert(!col.count({x, e}));
      tmp.eb(col[{x, e}] = U.back()), mp[i][U.back()] = {x, e};
      U.pop_back();
    }
    U.insert(U.end(), beg2ed(tmp));
  }
  // cerr << ssz(G[2]) << ' ' << ans << '\n';
  vector<int> todo;
  For(i, 1, n - 1) if (col[{G2[i][0].se, i}] == col[{G2[i][1].se, i}])
      todo.eb(i),
      is_todo[i] = 1;
  // cerr << "T " << ssz(todo) << ' ' << is_todo[850] << '\n';
  while (!todo.empty()) {
    int u = rnd() % ssz(todo), i = todo[u], j = rnd() & 1;
    // cerr << u << ' ' << i << ' ' << j << '\n';
    assert(is_todo[i]);
    assert((col[{G2[i][0].se, i}] == col[{G2[i][1].se, i}]));
    vector<int> his;
    int ban = col[{G2[i][j].se, i}];
    int ncol = rnd() % (ans - 1) + 1;
    if (ncol >= ban)
      ncol++, assert(ncol <= ans);
    assert(ncol != ban);
    while (1) {
      int to = G2[i][j].fi, x = G2[i][j].se;
      if (is_todo[i])
        his.eb(i);
      if (col[{x, i}] != ban)
        break;
      // cerr << "A " << x << ' ' << i << ' ' << to << ' ' << col[{x, i}] << "
      // -> "
      //      << ncol << '\n';
      col[{x, i}] = ncol, mp[to].erase(ban);
      if (!mp[to].count(ncol)) {
        mp[to][ncol] = {x, i};
        break;
      }
      pii e = exchange(mp[to][ncol], pii{x, i});
      // cerr << "B " << e.fi << ' ' << e.se << ' ' << to << ' ' << col[e]
      //      << " -> " << ban << '\n';
      mp[to][ban] = e, col[e] = ban;
      i = e.se, j = G2[i][0] == pii{to, e.fi};
    }
    for (int x : his)
      is_todo[x] = 0, todo.erase(find(beg2ed(todo), x));
  }
  For(i, 1, n) {
    printf("%d ", val[i]);
    for (int e : T[i])
      printf("%d ", col[{i, e}]);
    puts("");
  }
}
void Main() {
  read(Tc);
  while (Tc--)
    solve();
}
} // namespace

signed main() { return Main(), 0; }
0