結果

問題 No.2987 Colorful University of Tree
ユーザー 3663 bot
提出日時 2025-05-24 16:06:43
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 457 ms / 5,000 ms
コード長 4,342 bytes
コンパイル時間 5,855 ms
コンパイル使用メモリ 320,844 KB
実行使用メモリ 70,544 KB
最終ジャッジ日時 2025-05-24 16:07:06
合計ジャッジ時間 21,452 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 42
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i, j, k) for(int i = (j); i <= (k); i++)
#define per(i, j, k) for(int i = (j); i >= (k); i--)
#define pb emplace_back
#define fi first
#define se second
using vi = vector<int>;
using pi = pair<int, int>;

template<typename T0, typename T1> bool chmin(T0 &x, const T1 &y){
	if(y < x){x = y; return true;} return false;
}
template<typename T0, typename T1> bool chmax(T0 &x, const T1 &y){
	if(x < y){x = y; return true;} return false;
}

template<typename T> void debug(char *s, T x){
	cerr << s <<" = "<< x <<endl;
}
template<typename T, typename ...Ar> void debug(char *s, T x, Ar... y){
	int dep = 0;
	while(!(*s == ',' && dep == 0)){
		if(*s == '(') dep++;
		if(*s == ')') dep--;
		cerr << *s++;
	}
	cerr <<" = "<< x <<",";
	debug(s + 1, y...);
}
#define gdb(...) debug((char*)#__VA_ARGS__, __VA_ARGS__)

mt19937 rnd(time(0));

// 二分图匹配
vi match(int n, int m, vi ban){
	// bool ok = 0;
	// for(auto x:ban){
	// 	ok |= (x != -1);
	// }

	// gdb(n, ok, m);
	// if(n > m){
	// 	vi pre(m, -1), cur(n, 0), vis(n, 0);

	// 	auto dfs = [&](auto &self, int u)->bool {
	// 		if(vis[u]){
	// 			return false;
	// 		}
	// 		vis[u] = 1;
	// 		while(cur[u] < m){
	// 			int v = cur[u]++;
	// 			if(v == ban[u]){
	// 				continue;
	// 			}
	// 			if(pre[v] == -1){
	// 				pre[v] = u;
	// 				return true;
	// 			}
	// 			if(self(self, pre[v])){
	// 				pre[v] = u;
	// 				return true;
	// 			}
	// 		}
	// 		return false;
	// 	};

	// 	rep(i, 0, n - 1){
	// 		fill(cur.begin(), cur.end(), 0);
	// 		fill(vis.begin(), vis.end(), 0);
	// 		assert(dfs(dfs, i));
	// 	}
	// 	vi res(n, -1);
	// 	rep(i, 0, m - 1){
	// 		if(pre[i] != -1){
	// 			res[ pre[i] ] = i;
	// 		}
	// 	}
	// 	rep(i, 0, n - 1){
	// 		assert(res[i] != ban[i]);
	// 		assert(res[i] != -1);
	// 	}
	// 	return res;
	// }
	// else{
		vi res(min(n * 2, m), -1);
		while(1){
			iota(res.begin(), res.end(), 0);
			shuffle(res.begin(), res.end(), rnd);
			bool ok = 1;
			rep(i, 0, n - 1){
				ok &= res[i] != ban[i];
			}
			if(ok) break;
		}
		res.resize(n);
		return res;
	// }
}

void solve(){
	int n;
	cin >> n;
	vector<vi> G(n);
	rep(i, 0, n - 1){
		int d;
		cin >> d;
		G[i].resize(d);
		for(auto &c:G[i]){
			cin >> c;
			c--;
		}
	}

	int mx = 0;
	rep(i, 0, n - 1){
		chmax(mx, (int)G[i].size());
	}
	int ans = mx;
	while(ans * ans < (n - 1) * 2){
		ans++;
	}
	while(1){
		bool ok = 1;

		vi D;
		rep(i, 0, n - 1){
			D.pb(G[i].size());
		}
		sort(D.begin(), D.end(), greater<>());
		priority_queue<int> Q;
		rep(i, 0, ans - 1){
			Q.emplace(ans);
		}
		for(int x:D){
			if(Q.top() < x){
				ok = 0;
			}
			else{
				int t = Q.top() - x;
				Q.pop();
				Q.emplace(t);
			}
		}

		if(ok){
			break;
		}
		ans++;
	}
	
	cout << ans <<'\n';

	auto construct = [&](){
		vi ans0(n, -1), anse(n * 2 - 2, -1);
		vector<vi> ans1(n);
		rep(i, 0, n - 1){
			ans1[i].resize(G[i].size(), -1);
		}

		vector<vi> S(ans);
		
		vector<pi> D;
		rep(i, 0, n - 1){
			D.pb(G[i].size(), i);
		}
		sort(D.begin(), D.end(), greater<>());
		priority_queue<pi> Q;
		rep(i, 0, ans - 1){
			Q.emplace(ans, i);
		}
		for(auto [d, u]:D){
			auto [sz, id] = Q.top();
			Q.pop();
			S[id].pb(u);
			sz -= d;
			Q.emplace(sz, id);
		}

		stable_sort(S.begin(), S.end(), [&](const auto &A, const auto &B){
			int sa = 0, sb = 0;
			for(auto u:A) sa += G[u].size();
			for(auto u:B) sb += G[u].size();
			return sa > sb;
		});

		rep(i, 0, ans - 1){
			for(int j:S[i]){
				ans0[j] = i;
			}
		}
		rep(i, 0, ans - 1){
			map<int, int> id;
			vector<pi> U;
			for(int u:S[i]){
				for(int eid:G[u]){
					U.pb(eid, anse[eid]);
				}
			}
			vi ban(U.size(), -1);
			rep(j, 0, (int)U.size() - 1){
				id[ U[j].fi ] = j;
				ban[j] = U[j].se;
			}
			vi ansx = match(U.size(), ans, ban);
			int cnt = 0;
			for(int u:S[i]){
				rep(j, 0, (int)G[u].size() - 1){
					ans1[u][j] = ansx[cnt++];
				}
			}
			rep(j, 0, (int)U.size() - 1){
				anse[ U[j].fi ] = ansx[j];
			}
		}
		rep(i, 0, n - 1){
			cout << ans0[i] + 1 <<' ';
			rep(j, 0, (int)G[i].size() - 1){
				cout << ans1[i][j] + 1 <<' ';
			}
			cout <<'\n';
		}
	};
	construct();
}
signed main(){
	#ifdef LOCAL
	freopen(".in", "r", stdin);
	freopen(".out", "w", stdout);
	#endif
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int t;
	cin >> t;
	while(t--){
		solve();
	}
}
0