結果

問題 No.2998 Rainbow Christmas Tree
ユーザー 👑 ygussanyygussany
提出日時 2024-12-19 20:26:32
言語 C
(gcc 12.3.0)
結果
TLE  
(最新)
WA  
(最初)
実行時間 -
コード長 2,826 bytes
コンパイル時間 1,053 ms
コンパイル使用メモリ 33,152 KB
実行使用メモリ 11,392 KB
最終ジャッジ日時 2024-12-24 16:35:05
合計ジャッジ時間 124,372 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
10,496 KB
testcase_01 AC 1 ms
10,624 KB
testcase_02 AC 1 ms
10,496 KB
testcase_03 AC 1 ms
10,496 KB
testcase_04 AC 1 ms
10,496 KB
testcase_05 AC 2 ms
10,496 KB
testcase_06 AC 1 ms
10,496 KB
testcase_07 AC 1,724 ms
11,264 KB
testcase_08 AC 1,655 ms
11,008 KB
testcase_09 AC 1,465 ms
11,392 KB
testcase_10 AC 2,112 ms
11,008 KB
testcase_11 AC 1,915 ms
11,008 KB
testcase_12 AC 1,522 ms
10,880 KB
testcase_13 AC 2,363 ms
11,264 KB
testcase_14 AC 634 ms
11,008 KB
testcase_15 AC 1,638 ms
11,008 KB
testcase_16 AC 504 ms
11,008 KB
testcase_17 AC 1,210 ms
11,008 KB
testcase_18 TLE -
testcase_19 AC 116 ms
11,264 KB
testcase_20 AC 111 ms
11,008 KB
testcase_21 AC 109 ms
11,264 KB
testcase_22 AC 107 ms
11,008 KB
testcase_23 TLE -
testcase_24 AC 1,446 ms
11,008 KB
testcase_25 AC 553 ms
11,392 KB
testcase_26 TLE -
testcase_27 TLE -
testcase_28 TLE -
testcase_29 TLE -
testcase_30 TLE -
testcase_31 AC 1,363 ms
10,880 KB
testcase_32 AC 1,807 ms
10,880 KB
testcase_33 AC 2,710 ms
11,008 KB
testcase_34 TLE -
testcase_35 TLE -
testcase_36 TLE -
testcase_37 AC 249 ms
5,760 KB
testcase_38 TLE -
testcase_39 AC 112 ms
5,760 KB
testcase_40 AC 108 ms
5,760 KB
testcase_41 AC 109 ms
5,760 KB
testcase_42 AC 106 ms
5,632 KB
testcase_43 AC 148 ms
5,760 KB
testcase_44 AC 133 ms
5,632 KB
testcase_45 AC 1 ms
5,248 KB
testcase_46 AC 1 ms
5,248 KB
testcase_47 TLE -
testcase_48 AC 449 ms
5,760 KB
testcase_49 TLE -
testcase_50 TLE -
testcase_51 TLE -
testcase_52 TLE -
testcase_53 AC 845 ms
5,760 KB
testcase_54 TLE -
testcase_55 TLE -
testcase_56 TLE -
testcase_57 TLE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>
#include <stdlib.h>

#define N_MAX 1000

#define MT_N 624
#define MT_M 397
#define MT_MATRIX_A 0x9908b0dfUL
#define MT_UPPER_MASK 0x80000000UL
#define MT_LOWER_MASK 0x7fffffffUL

static unsigned int mt[MT_N];
static int mti = MT_N + 1;

void init_genrand(unsigned int s)
{
    mt[0] = s & 0xffffffffUL;
    for (mti = 1; mti < MT_N; mti++) {
        mt[mti] = (1812433253UL * (mt[mti-1] ^ (mt[mti-1] >> 30)) + mti); 
        mt[mti] &= 0xffffffffUL;
    }
}

unsigned int genrand()
{
    unsigned int y;
    static unsigned int mag01[2] = {0x0UL, MT_MATRIX_A};

    if (mti >= MT_N) {
        int kk;
        if (mti == MT_N + 1) init_genrand(5489UL);
		
        for (kk = 0; kk < MT_N - MT_M; kk++) {
            y = (mt[kk] & MT_UPPER_MASK) | (mt[kk+1] & MT_LOWER_MASK);
            mt[kk] = mt[kk+MT_M] ^ (y >> 1) ^ mag01[y&0x1UL];
        }
        for (; kk < MT_N - 1; kk++) {
            y = (mt[kk] & MT_UPPER_MASK) | (mt[kk+1] & MT_LOWER_MASK);
            mt[kk] = mt[kk+(MT_M-MT_N)] ^ (y >> 1) ^ mag01[y&0x1UL];
        }
        y = (mt[MT_N-1] & MT_UPPER_MASK) | (mt[0] & MT_LOWER_MASK);
        mt[MT_N-1] = mt[MT_M-1] ^ (y >> 1) ^ mag01[y&0x1UL];

        mti = 0;
    }
  
    y = mt[mti++];

    y ^= (y >> 11);
    y ^= (y << 7) & 0x9d2c5680UL;
    y ^= (y << 15) & 0xefc60000UL;
    y ^= (y >> 18);

    return y;
}

void shuffle_permutation(int N, int p[], int K)
{
	int i, j;
	while (K--) {
		i = genrand() % N + 1;
		j = genrand() % N + 1;
		if (i != j) {
			p[i] ^= p[j];
			p[j] ^= p[i];
			p[i] ^= p[j];
		}
	}
}

int is_arborescence(int N, int P[])
{
	int i, j, flag[N_MAX + 1] = {};
	for (j = 1; j <= N; j++) if (P[j] == 0) flag[j] = -1; // root
	for (i = 1; i <= N; i++) {
		if (flag[i] != 0) continue;
		for (j = i; flag[j] == 0; j = P[j]) flag[j] = 1;
		if (flag[j] > 0) return 0;
		for (j = i; flag[j] == 1; j = P[j]) flag[j] = -1;
	}
	return 1;
}

void solve_random(int N, int K, int P[][N_MAX + 1], int Q[])
{
	int i, j;
	static int p[N_MAX + 1], q[N_MAX + 1];
	for (i = 1; i <= N - 1; i++) p[i] = i;
	for (j = 1; j <= N; j++) q[j] = j;
	shuffle_permutation(N - 1, p, N * 10);
	shuffle_permutation(N, q, N * 10);
	while (1) {
		for (i = 0; i <= N; i++) Q[i] = -1;
		Q[genrand() % N + 1] = 0;
		for (i = 1; i <= N - 1; i++) {
			shuffle_permutation(N, q, N);
			for (j = 1; j <= N; j++) if (Q[P[p[i]][q[j]]] >= 0 && Q[q[j]] < 0) break;
			if (j > N) break;
			Q[q[j]] = p[i];
		}
		if (i > N - 1) break;
		shuffle_permutation(N - 1, p, N);
	}
}

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_random(N, K, P, Q);
	printf("Yes\n");
	for (j = 1; j <= N; j++) printf("%d ", Q[j]);
	printf("\n");
	fflush(stdout);
	return 0;
}
0