#1032405 (C) No.2998 Rainbow Christmas Tree

提出ソース

結果

問題	No.2998 Rainbow Christmas Tree
ユーザー	👑 ygussany
提出日時	2024-12-20 10:19:48
言語	C (gcc 12.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

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	1 ms 5,248 KB
testcase_02	AC	1 ms 5,248 KB
testcase_03	AC	1 ms 5,248 KB
testcase_04	AC	1 ms 5,248 KB
testcase_05	AC	1 ms 5,248 KB
testcase_06	AC	1 ms 5,248 KB
testcase_07	AC	102 ms 5,760 KB
testcase_08	AC	100 ms 5,888 KB
testcase_09	AC	102 ms 5,888 KB
testcase_10	AC	101 ms 5,760 KB
testcase_11	AC	101 ms 5,888 KB
testcase_12	AC	101 ms 5,760 KB
testcase_13	AC	101 ms 5,888 KB
testcase_14	AC	100 ms 5,760 KB
testcase_15	AC	102 ms 5,760 KB
testcase_16	AC	100 ms 5,760 KB
testcase_17	AC	101 ms 5,760 KB
testcase_18	AC	102 ms 5,760 KB
testcase_19	AC	98 ms 5,888 KB
testcase_20	AC	99 ms 5,760 KB
testcase_21	AC	101 ms 5,760 KB
testcase_22	AC	104 ms 5,760 KB
testcase_23	AC	100 ms 5,760 KB
testcase_24	AC	101 ms 5,888 KB
testcase_25	AC	101 ms 5,760 KB
testcase_26	AC	100 ms 5,760 KB
testcase_27	AC	102 ms 5,760 KB
testcase_28	AC	101 ms 5,760 KB
testcase_29	AC	104 ms 5,760 KB
testcase_30	AC	101 ms 5,632 KB
testcase_31	AC	101 ms 5,760 KB
testcase_32	AC	100 ms 5,888 KB
testcase_33	AC	101 ms 5,760 KB
testcase_34	AC	99 ms 5,888 KB
testcase_35	AC	102 ms 5,760 KB
testcase_36	AC	100 ms 5,760 KB
testcase_37	AC	100 ms 5,888 KB
testcase_38	AC	102 ms 5,888 KB
testcase_39	AC	104 ms 5,888 KB
testcase_40	AC	101 ms 5,888 KB
testcase_41	AC	100 ms 5,888 KB
testcase_42	AC	101 ms 5,760 KB
testcase_43	AC	101 ms 5,760 KB
testcase_44	AC	101 ms 5,888 KB
testcase_45	AC	1 ms 5,248 KB
testcase_46	AC	1 ms 5,248 KB
testcase_47	AC	100 ms 5,760 KB
testcase_48	AC	100 ms 5,760 KB
testcase_49	AC	102 ms 5,760 KB
testcase_50	AC	101 ms 5,760 KB
testcase_51	AC	101 ms 5,888 KB
testcase_52	AC	101 ms 5,760 KB
testcase_53	AC	100 ms 5,760 KB
testcase_54	AC	99 ms 5,760 KB
testcase_55	AC	101 ms 5,888 KB
testcase_56	AC	100 ms 5,760 KB
testcase_57	AC	101 ms 5,760 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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;
}

yukicoder

結果

テストケース

ソースコード