#718258 (C) No.1775 Love Triangle 2

提出ソース

結果

問題	No.1775 Love Triangle 2
ユーザー	👑 ygussany
提出日時	2021-11-19 23:52:57
言語	C (gcc 12.3.0)
結果	AC
実行時間	6,003 ms / 8,000 ms
コード長	5,254 bytes
コンパイル時間	1,342 ms
コンパイル使用メモリ	34,528 KB
実行使用メモリ	34,376 KB
最終ジャッジ日時	2023-09-18 00:33:46
合計ジャッジ時間	25,525 ms
ジャッジサーバーID （参考情報）	judge14 / judge15

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	4 ms 18,460 KB
testcase_01	AC	4 ms 16,260 KB
testcase_02	AC	5 ms 22,564 KB
testcase_03	AC	4 ms 18,428 KB
testcase_04	AC	6,003 ms 34,228 KB
testcase_05	AC	132 ms 30,956 KB
testcase_06	AC	132 ms 31,024 KB
testcase_07	AC	869 ms 32,076 KB
testcase_08	AC	108 ms 31,064 KB
testcase_09	AC	6 ms 16,532 KB
testcase_10	AC	7 ms 18,576 KB
testcase_11	AC	9 ms 30,964 KB
testcase_12	AC	8 ms 26,832 KB
testcase_13	AC	8 ms 20,636 KB
testcase_14	AC	14 ms 31,244 KB
testcase_15	AC	22 ms 31,304 KB
testcase_16	AC	24 ms 31,564 KB
testcase_17	AC	62 ms 32,316 KB
testcase_18	AC	227 ms 33,936 KB
testcase_19	AC	9 ms 31,056 KB
testcase_20	AC	6 ms 16,476 KB
testcase_21	AC	9 ms 30,840 KB
testcase_22	AC	10 ms 24,700 KB
testcase_23	AC	8 ms 20,624 KB
testcase_24	AC	9 ms 28,852 KB
testcase_25	AC	6 ms 16,640 KB
testcase_26	AC	10 ms 26,856 KB
testcase_27	AC	9 ms 30,924 KB
testcase_28	AC	11 ms 31,000 KB
testcase_29	AC	338 ms 34,340 KB
testcase_30	AC	502 ms 34,068 KB
testcase_31	AC	710 ms 33,660 KB
testcase_32	AC	681 ms 33,108 KB
testcase_33	AC	528 ms 32,700 KB
testcase_34	AC	526 ms 32,612 KB
testcase_35	AC	341 ms 32,444 KB
testcase_36	AC	156 ms 31,828 KB
testcase_37	AC	62 ms 31,616 KB
testcase_38	AC	9 ms 30,940 KB
testcase_39	AC	394 ms 34,244 KB
testcase_40	AC	610 ms 33,872 KB
testcase_41	AC	630 ms 33,508 KB
testcase_42	AC	472 ms 33,108 KB
testcase_43	AC	316 ms 32,736 KB
testcase_44	AC	223 ms 32,704 KB
testcase_45	AC	357 ms 32,440 KB
testcase_46	AC	102 ms 31,972 KB
testcase_47	AC	22 ms 31,756 KB
testcase_48	AC	23 ms 31,368 KB
testcase_49	AC	267 ms 34,376 KB
testcase_50	AC	491 ms 34,160 KB
testcase_51	AC	688 ms 33,560 KB
testcase_52	AC	645 ms 33,244 KB
testcase_53	AC	502 ms 32,800 KB
testcase_54	AC	512 ms 32,612 KB
testcase_55	AC	389 ms 32,440 KB
testcase_56	AC	175 ms 31,964 KB
testcase_57	AC	68 ms 31,612 KB
testcase_58	AC	12 ms 30,924 KB
testcase_59	AC	418 ms 34,180 KB
testcase_60	AC	498 ms 33,744 KB
testcase_61	AC	500 ms 33,504 KB
testcase_62	AC	224 ms 33,108 KB
testcase_63	AC	182 ms 32,800 KB
testcase_64	AC	156 ms 32,296 KB
testcase_65	AC	46 ms 32,032 KB
testcase_66	AC	34 ms 31,740 KB
testcase_67	AC	20 ms 31,348 KB
testcase_68	AC	9 ms 30,884 KB
testcase_69	AC	9 ms 28,784 KB
testcase_70	AC	11 ms 30,972 KB
testcase_71	AC	11 ms 30,972 KB
testcase_72	AC	10 ms 24,628 KB
testcase_73	AC	11 ms 30,876 KB
testcase_74	AC	9 ms 16,588 KB
testcase_75	AC	11 ms 30,972 KB
testcase_76	AC	10 ms 24,736 KB
testcase_77	AC	12 ms 30,896 KB
testcase_78	AC	9 ms 16,500 KB
testcase_79	AC	10 ms 30,920 KB
testcase_80	AC	10 ms 30,872 KB
testcase_81	AC	8 ms 16,504 KB
testcase_82	AC	8 ms 16,636 KB
testcase_83	AC	9 ms 16,504 KB
testcase_84	AC	11 ms 30,908 KB
testcase_85	AC	9 ms 16,636 KB
testcase_86	AC	9 ms 24,784 KB
testcase_87	AC	10 ms 22,676 KB
testcase_88	AC	9 ms 16,568 KB
testcase_89	AC	7 ms 16,632 KB

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

ソースコード

raw source code

#include <stdio.h>

#define N_MAX 100
#define M_MAX 5000



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

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



#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 3 // 3 -> 2^8, 4 -> 2^16, 5 -> 2^32
const unsigned int powd[5] = {2, 4, 16, 256, 65536}, powe[5] = {1, 2, 4, 8, 16};

// 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];
}



// Solution example (O(N^4) time by cumulative sum)
int solve4_2(int N, int M, int X, int Y, int Z, int A[], int B[])
{
	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 = e[i-1].label;
			e[i].next = adj[w];
			adj[w] = &(e[i++]);
		}
	}
	
	static int k, kk, l, x, y, z, cur, prev;
	static unsigned int dp[2][4][N_MAX + 1][N_MAX + 1][N_MAX + 1], tmp;
	for (k = 0; k < 4; k++) {
		for (p = adj[X]; p != NULL; p = p->next) {
			for (u = 1; u <= N; u++) {
				for (pp = adj[u]; pp != NULL; pp = pp->next) {
					dp[0][k][p->v][u][pp->v] = 0;
					dp[1][k][p->v][u][pp->v] = 0;
				}
			}
		}
	}
	for (p = adj[X]; p != NULL; p = p->next) {
		u = p->v;
		k = (u == Y)? 1: (u == Z)? 2: 0;
		dp[0][k][u][X][u] = p->label;
	}
	for (l = 2, cur = 1, prev = 0; l <= N; l++, cur ^= 1, prev ^= 1) {
		for (k = 0; k < 4; k++) {
			for (p = adj[X]; p != NULL; p = p->next) {
				w = p->v;
				for (y = 1; y <= N; y++) {
					for (pp = adj[y], tmp = 0; pp != NULL; pp = pp->next) {
						x = pp->v;
						tmp ^= dp[prev][k][w][x][y];
					}
					for (pp = adj[y]; pp != NULL; pp = pp->next) {
						z = pp->v;
						kk = k | ((z == Y)? 1: (z == Z)? 2: 0);
						if ((z == X && kk != 3) || (z == Y && (k & 1) != 0) || (z == Z && (k & 2) != 0)) continue;
						if (y == X || y == Y || y == Z) dp[cur][kk][w][y][z] ^= nim_product(tmp ^ dp[prev][k][w][z][y], pp->label);
						else dp[cur][kk][w][y][z] ^= nim_product(tmp, pp->label);
						dp[prev][k][w][z][y] = 0;
					}
				}
			}
		}
		for (p = adj[X]; p != NULL; p = p->next) {
			for (pp = p->next; pp != NULL; pp = pp->next) if (dp[cur][3][p->v][pp->v][X] != 0) break;
			if (pp != NULL) break;
		}
		if (p != NULL) break;
	}
	if (l > N) return -1;
	else return l;
}



int main()
{
	int i, N, M, X, Y, Z, A[M_MAX + 1], B[M_MAX + 1], ans[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]));
	ans[0] = solve4_2(N, M, X, Y, Z, A, B);
	// ans[1] = solve4_2(N, M, X, Y, Z, A, B);
	// chmin(&(ans[0]), ans[1]);
	printf("%d\n", (ans[0] > N)? -1: ans[0]);
	fflush(stdout);
	return 0;
}

yukicoder

結果

テストケース

ソースコード