結果

問題 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;
}
0