結果

問題 No.2998 Rainbow Christmas Tree
ユーザー rqoi031
提出日時 2025-05-27 16:13:17
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 15 ms / 3,000 ms
コード長 2,679 bytes
コンパイル時間 640 ms
コンパイル使用メモリ 64,136 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-05-27 16:13:33
合計ジャッジ時間 14,034 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 58
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<stdio.h>
#include<algorithm>
#include<cassert>
#define gc (zz==ZZ&&(zz=(ZZ=buf)+fread(buf,1,1<<20,stdin),zz==ZZ)?EOF:*ZZ++)
char buf[1<<20],*zz{buf},*ZZ{buf};
inline void read(char *s) {
    char ch(gc);
    while(ch<=32) {
        ch=gc;
    }
    while(ch>32) {
        *s++=ch,ch=gc;
    }
    *s='\0';
}
template<typename Tp>
inline void read(Tp &x) {
    x=0;char ch(gc);
    while(ch<=32) {
        ch=gc;
    }
    while(ch>32) {
        x=(x<<3)+(x<<1)+(ch^48),ch=gc;
    }
}
template<typename Tp,typename... Tps>
inline void read(Tp &x,Tps &...xs) {
    read(x),read(xs...);
}
#undef gc
constexpr int N{1000};
int fa[N+5][N+5];
int pre0[N+5],col0[N+5];
int pre1[N+5],col1[N+5];
int vis[N+5],ans[N+5];
int main() {
    int n,k;
    read(n,k);
    for(int i=1;i<=n-1;i++) {
        for(int j=1;j<=n;j++) {
            read(fa[i][j]);
        }
    }
    std::fill(pre0+1,pre0+n+1,0);
    std::fill(col0+1,col0+n+1,0);
    pre0[n]=n,col0[1]=0;
    for(int i=1;i<=k;i++) {
        for(int j=1;j<=n;j++) {
            if(pre0[j]!=0&&pre0[fa[i][j]]==0) {
                pre0[fa[i][j]]=j;
                col0[fa[i][j]]=i;
                break;
            }
        }
    }
    std::fill(pre1+1,pre1+n+1,0);
    std::fill(col1+1,col1+n+1,0);
    pre1[1]=1,col1[1]=0;
    for(int i=k+1;i<=n-1;i++) {
        for(int j=1;j<=n;j++) {
            if(pre1[j]!=0&&pre1[fa[i][j]]==0) {
                pre1[fa[i][j]]=j;
                col1[fa[i][j]]=i;
                break;
            }
        }
    }
    int rt{0};
    for(int i=1;i<=n;i++) {
        if(pre0[i]!=0&&pre1[i]!=0) {
            rt=i;
            break;
        }
    }
    assert(rt!=0);
    std::fill(vis+1,vis+n+1,0);
    vis[rt]=1;
    for(int i=rt;i!=n;i=pre0[i]) {
        vis[pre0[i]]=1;
    }
    for(int i=rt;i!=1;i=pre1[i]) {
        if(vis[pre1[i]]) {
            rt=pre1[i];
        }
    }
    std::fill(vis+1,vis+n+1,0);
    std::fill(ans+1,ans+n+1,0);
    ans[rt]=-1;
    for(int i=rt;i!=n;i=pre0[i]) {
        assert(vis[col0[i]]==0);
        vis[col0[i]]=1;
        assert(ans[pre0[i]]==0);
        ans[pre0[i]]=col0[i];
    }
    for(int i=rt;i!=1;i=pre1[i]) {
        assert(vis[col1[i]]==0);
        vis[col1[i]]=1;
        assert(ans[pre1[i]]==0);
        ans[pre1[i]]=col1[i];
    }
    for(int i=1;i<=n-1;i++) {
        if(vis[i]==1) {
            continue;
        }
        for(int j=1;j<=n;j++) {
            if(ans[j]==0&&ans[fa[i][j]]!=0) {
                ans[j]=i;
                break;
            }
        }
    }
    ans[rt]=0;
	puts("Yes");
    for(int i=1;i<=n;i++) {
        assert(i==rt||ans[i]!=0);
        printf("%d%c",ans[i],i==n?'\n':' ');
    }
	return 0;
}
0