#717511 (C) No.1776 Love Triangle 2 (Hard)

提出ソース

結果

問題	No.1776 Love Triangle 2 (Hard)
ユーザー	ygussany
提出日時	2021-11-19 18:40:20
言語	C (gcc 12.3.0)
結果	AC
実行時間	1,831 ms / 10,000 ms
コード長	7,953 bytes
コンパイル時間	463 ms
コンパイル使用メモリ	37,112 KB
実行使用メモリ	6,944 KB
最終ジャッジ日時	2024-07-06 21:16:38
合計ジャッジ時間	43,586 ms
ジャッジサーバーID （参考情報）	judge1 / judge4

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 6,816 KB
testcase_01	AC	1 ms 6,944 KB
testcase_02	AC	1 ms 6,944 KB
testcase_03	AC	1 ms 6,940 KB
testcase_04	AC	225 ms 6,940 KB
testcase_05	AC	432 ms 6,940 KB
testcase_06	AC	419 ms 6,940 KB
testcase_07	AC	121 ms 6,944 KB
testcase_08	AC	264 ms 6,940 KB
testcase_09	AC	10 ms 6,940 KB
testcase_10	AC	12 ms 6,940 KB
testcase_11	AC	9 ms 6,944 KB
testcase_12	AC	8 ms 6,940 KB
testcase_13	AC	8 ms 6,944 KB
testcase_14	AC	8 ms 6,940 KB
testcase_15	AC	9 ms 6,944 KB
testcase_16	AC	7 ms 6,944 KB
testcase_17	AC	9 ms 6,944 KB
testcase_18	AC	24 ms 6,944 KB
testcase_19	AC	10 ms 6,940 KB
testcase_20	AC	12 ms 6,944 KB
testcase_21	AC	11 ms 6,944 KB
testcase_22	AC	10 ms 6,944 KB
testcase_23	AC	8 ms 6,940 KB
testcase_24	AC	9 ms 6,944 KB
testcase_25	AC	8 ms 6,944 KB
testcase_26	AC	9 ms 6,944 KB
testcase_27	AC	9 ms 6,940 KB
testcase_28	AC	8 ms 6,940 KB
testcase_29	AC	35 ms 6,940 KB
testcase_30	AC	51 ms 6,944 KB
testcase_31	AC	177 ms 6,944 KB
testcase_32	AC	294 ms 6,940 KB
testcase_33	AC	376 ms 6,940 KB
testcase_34	AC	376 ms 6,940 KB
testcase_35	AC	363 ms 6,944 KB
testcase_36	AC	293 ms 6,944 KB
testcase_37	AC	190 ms 6,944 KB
testcase_38	AC	47 ms 6,944 KB
testcase_39	AC	29 ms 6,944 KB
testcase_40	AC	108 ms 6,940 KB
testcase_41	AC	167 ms 6,940 KB
testcase_42	AC	173 ms 6,940 KB
testcase_43	AC	147 ms 6,944 KB
testcase_44	AC	54 ms 6,944 KB
testcase_45	AC	394 ms 6,944 KB
testcase_46	AC	77 ms 6,944 KB
testcase_47	AC	10 ms 6,944 KB
testcase_48	AC	38 ms 6,940 KB
testcase_49	AC	12 ms 6,944 KB
testcase_50	AC	47 ms 6,944 KB
testcase_51	AC	154 ms 6,944 KB
testcase_52	AC	243 ms 6,944 KB
testcase_53	AC	305 ms 6,944 KB
testcase_54	AC	315 ms 6,944 KB
testcase_55	AC	305 ms 6,940 KB
testcase_56	AC	302 ms 6,940 KB
testcase_57	AC	169 ms 6,940 KB
testcase_58	AC	143 ms 6,944 KB
testcase_59	AC	32 ms 6,944 KB
testcase_60	AC	76 ms 6,944 KB
testcase_61	AC	105 ms 6,940 KB
testcase_62	AC	41 ms 6,944 KB
testcase_63	AC	42 ms 6,940 KB
testcase_64	AC	64 ms 6,944 KB
testcase_65	AC	10 ms 6,944 KB
testcase_66	AC	20 ms 6,944 KB
testcase_67	AC	26 ms 6,944 KB
testcase_68	AC	7 ms 6,940 KB
testcase_69	AC	764 ms 6,940 KB
testcase_70	AC	1,499 ms 6,940 KB
testcase_71	AC	1,450 ms 6,940 KB
testcase_72	AC	431 ms 6,944 KB
testcase_73	AC	940 ms 6,944 KB
testcase_74	AC	19 ms 6,940 KB
testcase_75	AC	15 ms 6,940 KB
testcase_76	AC	14 ms 6,940 KB
testcase_77	AC	12 ms 6,940 KB
testcase_78	AC	12 ms 6,940 KB
testcase_79	AC	11 ms 6,940 KB
testcase_80	AC	14 ms 6,940 KB
testcase_81	AC	13 ms 6,940 KB
testcase_82	AC	20 ms 6,940 KB
testcase_83	AC	50 ms 6,940 KB
testcase_84	AC	21 ms 6,944 KB
testcase_85	AC	17 ms 6,940 KB
testcase_86	AC	15 ms 6,944 KB
testcase_87	AC	12 ms 6,940 KB
testcase_88	AC	14 ms 6,944 KB
testcase_89	AC	17 ms 6,940 KB
testcase_90	AC	12 ms 6,940 KB
testcase_91	AC	12 ms 6,944 KB
testcase_92	AC	14 ms 6,944 KB
testcase_93	AC	14 ms 6,940 KB
testcase_94	AC	83 ms 6,940 KB
testcase_95	AC	192 ms 6,944 KB
testcase_96	AC	668 ms 6,944 KB
testcase_97	AC	1,377 ms 6,944 KB
testcase_98	AC	1,785 ms 6,944 KB
testcase_99	AC	1,831 ms 6,940 KB
testcase_100	AC	1,568 ms 6,944 KB
testcase_101	AC	1,024 ms 6,940 KB
testcase_102	AC	544 ms 6,940 KB
testcase_103	AC	155 ms 6,940 KB
testcase_104	AC	51 ms 6,940 KB
testcase_105	AC	221 ms 6,944 KB
testcase_106	AC	508 ms 6,944 KB
testcase_107	AC	95 ms 6,940 KB
testcase_108	AC	449 ms 6,944 KB
testcase_109	AC	111 ms 6,944 KB
testcase_110	AC	94 ms 6,940 KB
testcase_111	AC	79 ms 6,940 KB
testcase_112	AC	28 ms 6,944 KB
testcase_113	AC	41 ms 6,944 KB
testcase_114	AC	80 ms 6,944 KB
testcase_115	AC	165 ms 6,940 KB
testcase_116	AC	573 ms 6,944 KB
testcase_117	AC	1,144 ms 6,940 KB
testcase_118	AC	1,524 ms 6,944 KB
testcase_119	AC	1,516 ms 6,944 KB
testcase_120	AC	1,345 ms 6,940 KB
testcase_121	AC	821 ms 6,940 KB
testcase_122	AC	614 ms 6,944 KB
testcase_123	AC	527 ms 6,944 KB
testcase_124	AC	87 ms 6,940 KB
testcase_125	AC	89 ms 6,940 KB
testcase_126	AC	160 ms 6,944 KB
testcase_127	AC	86 ms 6,940 KB
testcase_128	AC	71 ms 6,940 KB
testcase_129	AC	54 ms 6,944 KB
testcase_130	AC	57 ms 6,940 KB
testcase_131	AC	53 ms 6,944 KB
testcase_132	AC	39 ms 6,944 KB
testcase_133	AC	24 ms 6,944 KB
testcase_134	AC	17 ms 6,940 KB
testcase_135	AC	69 ms 6,940 KB
testcase_136	AC	68 ms 6,940 KB
testcase_137	AC	60 ms 6,940 KB
testcase_138	AC	84 ms 6,940 KB
testcase_139	AC	137 ms 6,944 KB
testcase_140	AC	114 ms 6,940 KB
testcase_141	AC	67 ms 6,940 KB
testcase_142	AC	114 ms 6,940 KB
testcase_143	AC	82 ms 6,944 KB
testcase_144	AC	19 ms 6,940 KB
testcase_145	AC	22 ms 6,940 KB
testcase_146	AC	54 ms 6,944 KB
testcase_147	AC	22 ms 6,940 KB
testcase_148	AC	49 ms 6,944 KB
testcase_149	AC	40 ms 6,940 KB
testcase_150	AC	58 ms 6,940 KB
testcase_151	AC	26 ms 6,940 KB
testcase_152	AC	47 ms 6,944 KB
testcase_153	AC	74 ms 6,944 KB
testcase_154	AC	43 ms 6,940 KB
testcase_155	AC	202 ms 6,944 KB
testcase_156	AC	259 ms 6,940 KB
testcase_157	AC	152 ms 6,940 KB
testcase_158	AC	164 ms 6,940 KB
testcase_159	AC	215 ms 6,940 KB
testcase_160	AC	89 ms 6,940 KB
testcase_161	AC	134 ms 6,944 KB
testcase_162	AC	350 ms 6,940 KB
testcase_163	AC	387 ms 6,940 KB
testcase_164	AC	393 ms 6,940 KB
testcase_165	AC	178 ms 6,940 KB
testcase_166	AC	93 ms 6,940 KB
testcase_167	AC	102 ms 6,944 KB
testcase_168	AC	59 ms 6,940 KB
testcase_169	AC	102 ms 6,944 KB
testcase_170	AC	162 ms 6,940 KB
testcase_171	AC	253 ms 6,940 KB
testcase_172	AC	132 ms 6,940 KB
testcase_173	AC	349 ms 6,944 KB
testcase_174	AC	138 ms 6,944 KB
testcase_175	AC	149 ms 6,940 KB

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

ソースコード

raw source code

#include <stdio.h>

#define N_MAX 150
#define M_MAX 12000



typedef struct Edge {
	struct Edge *next;
	int v;
	unsigned int label;
} edge;

void chmin(int* a, int b)
{
	if (*a > b) *a = b;
}

int lex_smaller(int a[], int b[])
{
	int i;
	for (i = 0; i <= a[0]; i++) {
		if (a[i] < b[i]) return 1;
		else if (a[i] > b[i]) return -1;
	}
	return 0;
}

void chlexmin(int a[], int b[])
{
	int i;
	if (lex_smaller(a, b) < 0) for (i = 0; i <= b[0]; i++) a[i] = b[i];
}

void print_ans(int N, int ans[])
{
	int i;
	if (ans[0] > N) {
		printf("-1\n");
		return;
	} else printf("%d\n", ans[0]);
	for (i = 1; i <= ans[0]; i++) printf("%d ", ans[i]);
	printf("%d\n", ans[1]);
}



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



#define POWX 4 // 3 -> 2^8, 4 -> 2^16, 5 -> 2^32
const unsigned int powd[6] = {2, 4, 16, 256, 65536}, powe[6] = {1, 2, 4, 8, 16, 32};

// Multiplication on a finite field of size 2^32 with XOR addition
unsigned int nim_product(unsigned int A, unsigned int B)
{
	if (A > B) return nim_product(B, A);
	else if (A <= 1) return A * B;
	
	static unsigned int memo[256][256] = {};
	if (B < 256 && memo[A][B] != 0) return memo[A][B];
	
	int i;
	for (i = 0; i < POWX; i++) {
		if (B == powd[i]) {
			if (A == powd[i]) return (B >> 1) * 3;
			else return A * B;
		}
	}

	unsigned int a[2], b[2], ans[2][2];
	for (i = POWX - 1; i >= 0; i--) if (B > powd[i]) break;
	a[1] = A & (powd[i] - 1);
	a[0] = (A ^ a[1]) >> powe[i];
	b[1] = B & (powd[i] - 1);
	b[0] = (B ^ b[1]) >> powe[i];
	ans[0][0] = nim_product(a[0], b[0]);
	ans[0][1] = nim_product(a[0], b[1]);
	ans[1][0] = nim_product(a[1], b[0]);
	ans[1][1] = nim_product(a[1], b[1]);
	if (B < 256) {
		memo[A][B] = (ans[0][0] ^ ans[0][1] ^ ans[1][0]) * powd[i] ^ nim_product(ans[0][0], powd[i] >> 1) ^ ans[1][1];
		return memo[A][B];
	} else return (ans[0][0] ^ ans[0][1] ^ ans[1][0]) * powd[i] ^ nim_product(ans[0][0], powd[i] >> 1) ^ ans[1][1];
}



int solve4_lexmin_sub(int N, int X, int Y, int Z, edge* adj[], edge* d_adj[][N_MAX + 1], int s, int flag[])
{
	static int i, k, kk, l, n, u, w, x, y, z;
	static unsigned int dp[N_MAX + 1][4][N_MAX + 1], tmp;
	static edge *p;
	kk = ((flag[Y] != 0)? 1: 0) | ((flag[Z] != 0)? 2: 0);
	for (u = 1, n = 0; u <= N; u++) if (flag[u] == 0) n++;
	for (l = 0; l <= N; l++) for (k = 0; k < 4; k++) for (u = 1; u <= N; u++) dp[l][k][u] = 0;
	for (p = adj[X]; p != NULL; p = p->next) if (flag[p->v] == 0) dp[1][kk][p->v] = p->label;
	for (l = 1; l <= n; l++) {
		for (p = adj[s]; p != NULL; p = p->next) if (flag[p->v] == 0 && dp[l][3][p->v] != 0) break;
		if (p != NULL) break;
		if (flag[Y] == 0) {
			for (p = d_adj[1][s]; p != NULL; p = p->next) if (flag[p->v] == 0 && dp[l-1][2][p->v] != 0) break;
			if (p != NULL) break;
		}
		if (flag[Z] == 0) {
			for (p = d_adj[2][s]; p != NULL; p = p->next) if (flag[p->v] == 0 && dp[l-1][1][p->v] != 0) break;
			if (p != NULL) break;
		}
		if (l == n) return -1;
		
		for (k = 0; k < 4; k++) {
			if ((k & kk) != kk) continue;
			for (y = 1; y <= N; y++) {
				if (flag[y] != 0 || y == X || y == Y || y == Z) continue;
				tmp = dp[l][k][y];
				for (p = adj[y]; p != NULL; p = p->next) {
					z = p->v;
					dp[l+1][k][z] ^= nim_product(tmp, p->label);
				}
				if (l == n - 1) continue;
				if ((k & 1) == 0) {
					for (p = d_adj[1][y]; p != NULL; p = p->next) {
						z = p->v;
						dp[l+2][k|1][z] ^= nim_product(tmp, p->label);
					}
				}
				if ((k & 2) == 0) {
					for (p = d_adj[2][y]; p != NULL; p = p->next) {
						z = p->v;
						dp[l+2][k|2][z] ^= nim_product(tmp, p->label);
					}
				}
			}
		}
	}
	
	int ans = N + 1;
	for (p = adj[s]; p != NULL; p = p->next) if (flag[p->v] == 0 && dp[l][3][p->v] != 0) chmin(&ans, p->v);
	if (ans < Y) return ans;
	else if (flag[Y] == 0) for (p = d_adj[1][s]; p != NULL; p = p->next) if (flag[p->v] == 0 && dp[l-1][2][p->v] != 0) ans = Y;
	if (ans < Z) return ans;
	else if (flag[Z] == 0) for (p = d_adj[2][s]; p != NULL; p = p->next) if (flag[p->v] == 0 && dp[l-1][1][p->v] != 0) ans = Z;
	return ans;
}

// Solution example (O(N^4) time with all speeding-up) for finding the lexmin solution
int solve4_lexmin(int N, int M, int X, int Y, int Z, int A[], int B[], int ans[])
{
	static int i, u, w, adj_mat[N_MAX + 1][N_MAX + 1];
	static edge *adj[N_MAX + 1], e[M_MAX * 2], *p, *pp;
	for (u = 1; u <= N; u++) for (w = u + 1; w <= N; w++) adj_mat[u][w] = 0;
	for (i = 1; i <= M; i++) {
		u = A[i];
		w = B[i];
		adj_mat[u][w] = 1;
	}
	for (u = 1; u <= N; u++) adj[u] = NULL;
	for (u = 1, i = 0; u <= N; u++) {
		for (w = u + 1; w <= N; w++) {
			if (adj_mat[u][w] != 0) continue;
			e[i].v = w;
			e[i].label = genrand() % (powd[POWX] - 1) + 1;
			e[i].next = adj[u];
			adj[u] = &(e[i++]);
			e[i].v = u;
			e[i].label = (u == X || w == X)? genrand() % (powd[POWX] - 1) + 1: e[i-1].label;
			e[i].next = adj[w];
			adj[w] = &(e[i++]);
		}
	}
	
	static edge *d_adj[3][N_MAX + 1], f[N_MAX * N_MAX * 2];
	for (u = 1; u <= N; u++) {
		d_adj[1][u] = NULL;
		d_adj[2][u] = NULL;
	}
	for (p = adj[Y], i = 0; p != NULL; p = p->next) {
		u = p->v;
		for (pp = p->next; pp != NULL; pp = pp->next) {
			w = pp->v;
			f[i].v = w;
			f[i].label = nim_product(p->label, pp->label);
			f[i].next = d_adj[1][u];
			d_adj[1][u] = &(f[i++]);
			f[i].v = u;
			f[i].label = f[i-1].label;
			f[i].next = d_adj[1][w];
			d_adj[1][w] = &(f[i++]);
		}
	}
	for (p = adj[Z]; p != NULL; p = p->next) {
		u = p->v;
		for (pp = p->next; pp != NULL; pp = pp->next) {
			w = pp->v;
			f[i].v = w;
			f[i].label = nim_product(p->label, pp->label);
			f[i].next = d_adj[2][u];
			d_adj[2][u] = &(f[i++]);
			f[i].v = u;
			f[i].label = f[i-1].label;
			f[i].next = d_adj[2][w];
			d_adj[2][w] = &(f[i++]);
		}
	}
	
	static int flag[N_MAX + 1];
	for (u = 1; u <= N; u++) flag[u] = 0;
	ans[1] = X;
	ans[2] = solve4_lexmin_sub(N, X, Y, Z, adj, d_adj, X, flag);
	if (ans[2] < 0) {
		ans[0] = N + 1;
		for (i = 1; i <= N + 1; i++) ans[i] = 0;
		return -1;
	} else ans[0] = 2;
	flag[ans[1]] = 1;
	flag[ans[2]] = 1;
	while (1) {
		u = ans[ans[0]];
		if (flag[Y] != 0 && flag[Z] != 0) {
			for (p = adj[u]; p != NULL; p = p->next) if (p->v == X) break;
			if (p != NULL) break;
		}
		w = solve4_lexmin_sub(N, X, Y, Z, adj, d_adj, u, flag);
		flag[w] = 1;
		ans[++ans[0]] = w;
	}
	return ans[0];
}



int main()
{
	int i, N, M, X, Y, Z, A[M_MAX + 1], B[M_MAX + 1], ans[2][N_MAX + 2];
	scanf("%d %d", &N, &M);
	scanf("%d %d %d", &X, &Y, &Z);
	for (i = 1; i <= M; i++) scanf("%d %d", &(A[i]), &(B[i]));
	solve4_lexmin(N, M, X, Y, Z, A, B, ans[0]);
	solve4_lexmin(N, M, X, Y, Z, A, B, ans[1]);
	chlexmin(ans[0], ans[1]);
	// solve4_lexmin(N, M, X, Y, Z, A, B, ans[1]);
	// chlexmin(ans[0], ans[1]);
	print_ans(N, ans[0]);
	fflush(stdout);
	return 0;
}

yukicoder

結果

テストケース

ソースコード