結果

問題 No.2987 Colorful University of Tree
コンテスト
ユーザー Enucai
提出日時 2025-05-24 11:52:20
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 161 ms / 5,000 ms
コード長 2,310 bytes
コンパイル時間 2,319 ms
コンパイル使用メモリ 209,516 KB
実行使用メモリ 29,192 KB
最終ジャッジ日時 2025-05-24 11:52:45
合計ジャッジ時間 21,817 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 42
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#define LL long long
#define LLL __int128
#define uint unsigned
#define ldb long double
#define uLL unsigned long long
using namespace std;
const int N=2e5+5;
int n,ans,cnt;
vector<int>F[N];
pair<int,int>E[N];
vector<pair<int,int>>G[N];
int id[N],A[N],B[N],C[N],sz[N],lst[N];
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
inline bool solve(){
  cnt=0;
  iota(id+1,id+n+1,1);
  sort(id+1,id+n+1,[&](int x,int y){
    return G[x].size()>G[y].size();
  });
  int r=n;
  while(G[id[r]].size()==1)--r;
  for(int i=1;i<=r;++i){
    ++cnt;
    sz[cnt]=G[id[i]].size();
    F[cnt].emplace_back(id[i]);
    for(;i<r&&sz[cnt]+G[id[r]].size()<=ans;sz[cnt]+=G[id[r]].size(),--r)F[cnt].emplace_back(id[r]);
  }
  for(int i=1,j=1;i<=n;++i)if(G[i].size()==1){
    while(sz[j]>=ans)++j;
    F[j].emplace_back(i),++sz[j];
    if(j>cnt)++cnt;
  }
  if(cnt>ans){
    for(int i=1;i<=cnt;++i)F[i].clear(),sz[i]=0;
    return 0;
  }
  for(int i=1;i<=cnt;++i){
    vector<int>S;
    for(int u:F[i])A[u]=i;
    for(;;){
      S.clear();
      for(int j=1;j<=ans;++j)S.emplace_back(j);
      shuffle(S.begin(),S.end(),rng);
      int ok=1;
      for(int u:F[i])for(auto [v,w]:G[u]){
        int c=(u==E[w].first?C[w]:B[w]);
        if(!c)c=lst[v];
        if(c==S.back()&&S.size()==1){ok=0;break;}
        int d=(c==S.back()?S.end()[-2]:S.back());
        if(d!=S.back())S.erase(S.end()-2);
        else S.pop_back();
        (u==E[w].first?B[w]:C[w])=d,lst[v]=d;
      }
      if(ok)break;
      for(int u:F[i])for(auto [v,w]:G[u])(u==E[w].first?B[w]:C[w])=0;
    }
  }
  return 1;
}
void work() {
  cin>>n,ans=cnt=0;
  for(int i=1;i<n;i++) E[i]=make_pair(0,0);
  for(int i=1;i<=n;i++) F[i].clear(),id[i]=A[i]=B[i]=C[i]=sz[i]=lst[i]=0;
  for(int u=1;u<=n;++u){
    int d;cin>>d,G[u].resize(d);
    for(auto&[v,w]:G[u])
      cin>>w,(E[w].first?E[w].second:E[w].first)=u;
    ans=max(ans,d);
  }
  for(int u=1;u<=n;++u)for(auto&[v,w]:G[u])
    v=E[w].first^E[w].second^u;
  while(1ll*ans*ans<(n-1)*2)++ans;
  if(!solve())++ans,solve();
  cout<<ans<<'\n';
  for(int u=1;u<=n;++u){
    cout<<A[u];
    for(auto&[v,w]:G[u])cout<<' '<<(u==E[w].first?B[w]:C[w]);
    cout<<'\n';
  }
}
signed main(){
  cin.tie(0)->sync_with_stdio(0);
  int t;
  cin>>t;
  while(t--) work();
  return 0;
}
/*
*/
0