結果

問題 No.2998 Rainbow Christmas Tree
ユーザー 👑 ygussany
提出日時 2024-12-20 10:19:48
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 104 ms / 3,000 ms
コード長 1,554 bytes
コンパイル時間 587 ms
コンパイル使用メモリ 31,744 KB
実行使用メモリ 5,888 KB
最終ジャッジ日時 2024-12-23 17:32:12
合計ジャッジ時間 14,555 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 58
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <stdio.h>
#include <stdlib.h>
#define N_MAX 1000
void solve(int N, int K, int P[][N_MAX + 1], int Q[])
{
    int i, j, jj, q[N_MAX + 1][2], flag[N_MAX + 1] = {};
    for (i = 1; i <= N; i++) Q[i] = -1;
    flag[1] = 1;
    flag[N] = N;
    for (i = 1; i <= K; i++) {
        for (j = 2; j <= N; j++) if (flag[P[i][j]] != N && flag[j] == N) break;
        if (flag[P[i][j]] == 0) {
            flag[P[i][j]] = N;
            q[P[i][j]][0] = i;
            q[P[i][j]][1] = j;
        } else break;
    }
    if (i <= K) {
        Q[P[i][j]] = 0;
        Q[j] = i;
        for (jj = j; jj != N; jj = q[jj][1]) Q[q[jj][1]] = q[jj][0];
    } else {
        for (i = K + 1; i <= N - 1; i++) {
            for (j = 1; j <= N - 1; j++) if (flag[P[i][j]] != 1 && flag[j] == 1) break;
            if (flag[P[i][j]] == 0) {
                flag[P[i][j]] = 1;
                q[P[i][j]][0] = i;
                q[P[i][j]][1] = j;
            } else break;
        }
        Q[P[i][j]] = 0;
        Q[j] = i;
        for (jj = P[i][j]; jj != N; jj = q[jj][1]) Q[q[jj][1]] = q[jj][0];
        for (jj = j; jj != 1; jj = q[jj][1]) Q[q[jj][1]] = q[jj][0];
    }
    
    for (i = 1; i <= N - 1; i++) flag[i] = 0;
    for (j = 1; j <= N; j++) if (Q[j] > 0) flag[Q[j]] = 1;
    for (i = 1; i <= N - 1; i++) {
        if (flag[i] != 0) continue;
        for (j = 1; j <= N; j++) if (P[i][j] != 0 && Q[P[i][j]] >= 0 && Q[j] < 0) break;
        Q[j] = i;
    }
}
int main()
{
    int i, j, N, K;
    static int P[N_MAX + 1][N_MAX + 1];
    scanf("%d %d", &N, &K);
    for (i = 1; i <= N - 1; i++) for (j = 1; j <= N; j++) scanf("%d", &(P[i][j]));
    
    int Q[N_MAX + 1];
    solve(N, K, P, Q);
    printf("Yes\n");
    for (j = 1; j <= N; j++) printf("%d ", Q[j]);
    printf("\n");
    fflush(stdout);
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0