結果

問題 No.2987 Colorful University of Tree
ユーザー Zhang Letao
提出日時 2025-05-24 16:07:59
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 474 ms / 5,000 ms
コード長 4,709 bytes
コンパイル時間 2,720 ms
コンパイル使用メモリ 217,964 KB
実行使用メモリ 58,084 KB
最終ジャッジ日時 2025-05-24 16:08:21
合計ジャッジ時間 20,420 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 42
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<int, int> pii;

namespace IO {
	const int maxn = 1 << 20;
	
	char ibuf[maxn], *iS, *iT, obuf[maxn], *oS = obuf;

	inline char gc() {
		return (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, maxn, stdin), (iS == iT ? EOF : *iS++) : *iS++);
	}

	template<typename T = int>
	inline T read() {
		char c = gc();
		T x = 0;
		bool f = 0;
		while (c < '0' || c > '9') {
			f |= (c == '-');
			c = gc();
		}
		while (c >= '0' && c <= '9') {
			x = (x << 1) + (x << 3) + (c ^ 48);
			c = gc();
		}
		return f ? ~(x - 1) : x;
	}
	
	inline int reads(char *s) {
		char c = gc();
		int len = 0;
		while (isspace(c)) {
			c = gc();
		}
		while (!isspace(c)) {
			s[len++] = c;
			c = gc();
		}
		return len;
	}

	inline void flush() {
		fwrite(obuf, 1, oS - obuf, stdout);
		oS = obuf;
	}
	
	struct Flusher {
		~Flusher() {
			flush();
		}
	} AutoFlush;

	inline void pc(char ch) {
		if (oS == obuf + maxn) {
			flush();
		}
		*oS++ = ch;
	}

	template<typename T>
	inline void write(T x) {
		static char stk[64], *tp = stk;
		if (x < 0) {
			x = ~(x - 1);
			pc('-');
		}
		do {
			*tp++ = x % 10;
			x /= 10;
		} while (x);
		while (tp != stk) {
			pc((*--tp) | 48);
		}
	}
	
	template<typename T>
	inline void writesp(T x) {
		write(x);
		pc(' ');
	}
	
	template<typename T>
	inline void writeln(T x) {
		write(x);
		pc('\n');
	}
}

using IO::read;
using IO::reads;
using IO::write;
using IO::pc;
using IO::writesp;
using IO::writeln;

const int maxn = 200100;

int n, ps[maxn], ord[maxn];
pair<pii, pii> e[maxn];
vector<int> G[maxn], T[maxn], vc[maxn];
int a[maxn], b[maxn], tot, c[maxn], g[maxn];
pii h[maxn];

inline bool check(int x) {
	priority_queue< pii, vector<pii>, greater<pii> > pq;
	for (int i = 1; i <= x; ++i) {
		pq.emplace(0, i);
	}
	for (int _ = 1; _ <= n; ++_) {
		int u = ord[_];
		pii p = pq.top();
		pq.pop();
		if ((int)G[u].size() + p.fst > x) {
			return 0;
		}
		a[u] = p.scd;
		pq.emplace((int)G[u].size() + p.fst, p.scd);
	}
	return 1;
}

void solve() {
	n = read();
	for (int i = 1; i <= n; ++i) {
		vector<int>().swap(G[i]);
		vector<int>().swap(vc[i]);
	}
	int l = ceil(sqrt(n * 2 - 2));
	int r = min((int)sqrt(n * 4 - 4) + 2, n);
	for (int i = 1; i < n; ++i) {
		e[i] = mkp(mkp(0, 0), mkp(0, 0));
	}
	for (int i = 1, k, x; i <= n; ++i) {
		k = read();
		l = max(l, k);
		while (k--) {
			x = read();
			G[i].pb(x);
			if (!e[x].fst.fst) {
				e[x].fst = mkp(i, (int)G[i].size() - 1);
			} else {
				e[x].scd = mkp(i, (int)G[i].size() - 1);
			}
		}
		ord[i] = i;
	}
	sort(ord + 1, ord + n + 1, [&](const int &x, const int &y) {
		return G[x].size() > G[y].size();
	});
	int ans = l;
	while (l <= r) {
		int mid = (l + r) >> 1;
		if (check(mid)) {
			ans = mid;
			r = mid - 1;
		} else {
			l = mid + 1;
		}
	}
	writeln(ans);
	check(ans);
	for (int i = 1; i <= n; ++i) {
		vc[a[i]].pb(i);
	}
	for (int i = 1; i <= n; ++i) {
		vector<int>(G[i].size()).swap(T[i]);
	}
	set<pii> S;
	for (int i = 1; i <= ans; ++i) {
		S.emplace(0, i);
	}
	for (int i = 1; i <= ans; ++i) {
		tot = 0;
		for (int j = 0; j < (int)vc[i].size(); ++j) {
			int u = vc[i][j];
			for (int l = 0; l < (int)G[u].size(); ++l) {
				int k = G[u][l];
				pii p = (e[k].fst.fst == u) ? e[k].scd : e[k].fst;
				h[++tot] = mkp(u, l);
				b[tot] = T[p.fst][p.scd];
				if (b[tot]) {
					S.erase(mkp(g[b[tot]], b[tot]));
					++g[b[tot]];
					S.emplace(g[b[tot]], b[tot]);
				}
			}
		}
		auto it = S.begin();
		bool fl = 1;
		for (int j = 1; j <= tot; ++j) {
			c[j] = (it++)->scd;
			fl &= (c[j] == b[j]);
		}
		if (fl) {
			int t = c[1];
			for (int j = 1; j < tot; ++j) {
				c[j] = c[j + 1];
			}
			c[tot] = t;
		} else {
			int tt = 0;
			for (int j = 1; j <= tot; ++j) {
				if (c[j] == b[j]) {
					ps[++tt] = j;
				}
			}
			for (int j = 1; j < tt; j += 2) {
				swap(c[ps[j]], c[ps[j + 1]]);
			}
			if (tt & 1) {
				int k = ps[tt];
				for (int j = 1; j <= tot; ++j) {
					if (j == k) {
						continue;
					}
					if (c[j] != b[k] && c[k] != b[j]) {
						swap(c[j], c[k]);
						break;
					}
				}
			}
		}
		for (int j = 1; j <= tot; ++j) {
			T[h[j].fst][h[j].scd] = c[j];
			if (b[j]) {
				S.erase(mkp(g[b[j]], b[j]));
				--g[b[j]];
				S.emplace(g[b[j]], b[j]);
			}
		}
	}
	for (int i = 1; i <= n; ++i) {
		writesp(a[i]);
		for (int j = 0; j < (int)T[i].size(); ++j) {
			write(T[i][j]);
			pc(" \n"[j == (int)T[i].size() - 1]);
		}
	}
}

int main() {
	int T = read();
	while (T--) {
		solve();
	}
	return 0;
}
0