結果

問題 No.2987 Colorful University of Tree
ユーザー dyj133446
提出日時 2025-05-24 16:08:51
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 525 ms / 5,000 ms
コード長 2,330 bytes
コンパイル時間 4,921 ms
コンパイル使用メモリ 201,912 KB
実行使用メモリ 127,756 KB
最終ジャッジ日時 2025-05-24 16:09:15
合計ジャッジ時間 21,009 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 42
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
mt19937 rnd(114514);
int T,n,d[N],id[N],cnt[N],ans,rt[N],ls[N*50],rs[N*50],tree[N*50],tot1,c[N],p1[N],p2[N];
vector<int>v1[N],e[N],g[N],col[N];
bool Check;
bool cmp(int x,int y){return d[x]<d[y];}
bool check(int x)
{
	for(int i=0;i<=n;i++)col[i].clear();
	for(int i=1;i<=x;i++)col[0].emplace_back(i);
	int l=0;
	for(int i=n;i;i--)
	{
		while(l<=x&&!col[l].size())l++;
		if(l+d[id[i]]>x)return false;
		c[id[i]]=col[l].back();
		col[l+d[id[i]]].emplace_back(col[l].back()),col[l].pop_back();
	}
	return true;
}
void change(int &x,int l,int r,int pos)
{
	if(!x)x=++tot1,ls[x]=rs[x]=tree[x]=0;
	tree[x]++;
	if(l==r)return;
	int mid=(l+r)/2;
	if(pos<=mid)change(ls[x],l,mid,pos);
	else change(rs[x],mid+1,r,pos);
}
int solve(int x,int l,int r,int k)
{
	if(l==r)return l;
	int mid=(l+r)/2,val=mid-l+1-tree[ls[x]];
	if(val<k)return solve(rs[x],mid+1,r,k-val);
	return solve(ls[x],l,mid,k);
}
void dfs(int x,int prt,int col1)
{
	int tot=-1;
	for(auto y:e[x])
	{
		tot++;
		if(y==prt)
		{
			int al=ans-tree[rt[c[x]]],k=rnd()%al+1;
			int v=solve(rt[c[x]],1,ans,k);
			if(col1==v)v=solve(rt[c[x]],1,ans,k%al+1);
			if(col1==v)Check=1;
			g[x][tot]=v,change(rt[c[x]],1,ans,v);
		}
	}
	tot=-1;
	for(auto y:e[x])
	{
		tot++;
		if(y!=prt)
		{
			int al=ans-tree[rt[c[x]]],k=rnd()%al+1;
			int v=solve(rt[c[x]],1,ans,k);
			g[x][tot]=v,change(rt[c[x]],1,ans,v),dfs(y,x,v);
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>T;
	while(T--)
	{
		cin>>n;
		for(int i=1;i<=n;i++)v1[i].clear(),e[i].clear(),g[i].clear(),p1[i]=p2[i]=0;
		for(int i=1;i<=n;i++)
		{
			cin>>d[i],id[i]=i;
			for(int j=1,x;j<=d[i];j++)
			{
				cin>>x,v1[i].emplace_back(x);
				if(!p1[x])p1[x]=i;
				else p2[x]=i;
			}
			g[i].resize(v1[i].size());
		}
		for(int i=1;i<=n;i++)
		{
			for(auto j:v1[i])
			{
				if(p1[j]==i)e[i].emplace_back(p2[j]);
				else e[i].emplace_back(p1[j]);
			}
		}
		sort(id+1,id+n+1,cmp);
		int l=1,r=n;
		while(l<=r)
		{
			int mid=(l+r)/2;
			if(check(mid))r=mid-1;
			else l=mid+1;
		}
		cout<<l<<'\n',check(l);
		ans=l;
		while(1)
		{
			for(int i=1;i<=n;i++)rt[i]=0;
			tot1=Check=0,dfs(1,0,-1);
			if(!Check)break;
		}
		for(int i=1;i<=n;i++)
		{
			cout<<c[i]<<' ';
			for(auto j:g[i])cout<<j<<' ';
			cout<<'\n';
		}	
	}
	return 0;
}
0