結果

問題 No.271 next_permutation (2)
ユーザー hjxhjx
提出日時 2025-05-24 18:32:01
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
RE  
実行時間 -
コード長 2,974 bytes
コンパイル時間 1,895 ms
コンパイル使用メモリ 178,932 KB
実行使用メモリ 25,324 KB
最終ジャッジ日時 2025-05-24 18:32:08
合計ジャッジ時間 6,808 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other RE * 6 TLE * 1 -- * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define ll long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;

inline static int read(){
    int sum=0,neg=0,ch=getchar();
    while(!isdigit(ch)) neg|=(ch=='-'),ch=getchar();
    while(isdigit(ch)) sum=sum*10+(ch^48),ch=getchar();
    return neg?-sum:sum;
}

vector<int>e[200005],Ans[200005]; int n,id[200005],head[200005],ecnt;
struct{int v,w,nxt;}_e[400005]; int col[200005],ptr[200005],eid[200005];
void _add(int u,int v,int w){_e[++ecnt]={v,w,head[u]},head[u]=ecnt;}
void add(int u,int v,int i,int j){_add(u,v,i),_add(v,u,j);}
int dfs(int u,int fa){
    for(int&x:Ans[u]) x=++ptr[col[u]]; vector<int>vec; int e2f=0;
    for(int i=head[u];i;i=_e[i].nxt){
        int v=_e[i].v; if(v==fa){e2f=_e[i].w; continue;}
        if(dfs(v,u)==Ans[u][_e[i].w]) vec.push_back(_e[i].w);
    }
    if(vec.size()&1) vec.push_back(e2f);
    for(int i=0;i<vec.size();i+=2)
        swap(Ans[u][vec[i]],Ans[u][vec[i+1]]);
    return Ans[u][e2f];
}
set<pair<int,int>>Set; int ord[200005];
vector<int>leaf;
bool check(int Q,int rt){
    Set.clear(); int _rt=_e[head[rt]].v; for(int i=2;i<=Q;i++) Set.emplace(Q,i);
    col[rt]=col[_rt]=1,Set.emplace(Q-e[rt].size()-e[_rt].size(),1);
    for(int _i=1,i=ord[1];_i<=n;i=ord[++_i]) if(i!=rt && i!=_rt){
        auto it=prev(Set.end()); if(it->first<e[i].size()) return 0;
        Set.emplace(it->first-e[i].size(),col[i]=it->second),Set.erase(it);
    } return 1;
}
signed main(){
    // freopen("hjx.in","r",stdin);
    // freopen("hjx.out","w",stdout);
    for(int T=read();T;T--){
        n=read(),leaf.clear(),memset(head,ecnt=0,4*n+4); int C=0,rt=0;
        memset(id,0,4*n),memset(eid,0,4*n),memset(ptr,0,4*n+4);
        for(int i=1,k;i<=n;i++){
            k=read(),e[i].assign(k,0),Ans[i]=e[i],C=max(k,C); if(k==1) leaf.push_back(i);
            for(int j=0,t;j<k;j++){
                t=e[i][j]=read(); if(id[t]) add(id[t],i,eid[t],j); else id[t]=i,eid[t]=j;
            }
        }
        if(n==2){puts("2\n1 1\n2 2"); continue;}
        else if(C==n-1){
            printf("%d\n",C);
            for(int i=1;i<=n;i++) if(e[i].size()==C){
                for(int j=0;j<C;j++) col[e[i][j]]=j+1; break;
            }
            for(int i=1;i<=n;i++) if(e[i].size()==C){
                printf("1 ");
                for(int j=1;j<=C;j++) printf("%d ",j); puts("");
            }else printf("2 %d\n",col[e[i][0]]%C+1);
            continue;
        }
        for(int i:leaf){int v=_e[head[i]].v; if(!rt || e[v].size()<e[_e[head[rt]].v].size()) rt=i;}
        int l=e[rt].size()+e[_e[head[rt]].v].size(),r=n-1,Q; iota(ord+1,ord+n+1,1);
        sort(ord+1,ord+n+1,[](int x,int y){return e[x].size()>e[y].size();}); // 这里会不会有什么特殊性质？
        while(l<=r) if(check(Q=(l+r)>>1,rt)) r=Q-1; else l=Q+1;
        printf("%d\n",Q=l),check(Q,rt),dfs(rt,0);
        for(int i=1;i<=n;puts(""),i++){printf("%d ",col[i]); for(int j:Ans[i]) printf("%d ",j);}
    } return 0;
}
0