結果
問題 | No.2998 Rainbow Christmas Tree |
ユーザー |
👑 |
提出日時 | 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 |
ソースコード
#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; }