結果

問題 No.1776 Love Triangle 2 (Hard)
ユーザー ygussany
提出日時 2021-11-24 13:15:17
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 2,738 ms / 10,000 ms
コード長 7,608 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 721 ms
コンパイル使用メモリ 37,264 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-06 21:15:53
合計ジャッジ時間 60,922 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 176
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <stdio.h>

#define K_MAX 3
#define BIT_K_MAX 4
#define N_MAX 150
#define M_MAX 12000

const int bit[6] = {1, 2, 4, 8, 16, 32};

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

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

int complement_graph(int N, int M, int A[], int B[], edge* adj[], edge e[])
{
	static char adj_mat[N_MAX + 1][N_MAX + 1];
	static int i, u, w;
	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].id = i;
			e[i].next = adj[u];
			adj[u] = &(e[i++]);
			e[i].v = u;
			e[i].id = i;
			e[i].next = adj[w];
			adj[w] = &(e[i++]);
		}
	}
	return i / 2;
}

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



// Computing the lexicographically-minimum shortest s-t path through K specified vertices in O(2^K L^2 M) time
int lexmin_shortest_path_through_specified_vertices(int N, edge* adj[], edge e[], int s, int t, int K, char flag[], int ans[], int rep)
{
	static int i, k_done, u, w, n, v[N_MAX + 1];
	for (u = 1, n = 0, k_done = 0; u <= N; u++) {
		if (flag[u] > -2) v[++n] = u; // living vertices
		else if (flag[u] < -2) k_done |= bit[-3 - flag[u]]; // dead terminals
	}
	static int h, j, k, l, l_ans, cur, prev;
	static unsigned int dp[2][BIT_K_MAX][M_MAX * 2], tmp;
	static edge *p;
	for (j = 1, l_ans = n + 1; j <= rep; j++) {
		for (i = 1; i <= n; i++) {
			u = v[i];
			for (p = adj[u]; p != NULL; p = p->next) {
				w = p->v;
				if (flag[w] > -2 && w < u) continue;
				p->label = genrand() % (powd[POWX] - 1) + 1;
				if (u != t && w != t) e[p->id ^ 1].label = p->label; 
				else e[p->id ^ 1].label = genrand() % (powd[POWX] - 1) + 1; // around t
			}
		}
		
		for (k = 0; k < bit[K]; k++) {
			if ((k & k_done) != k_done) continue;
			for (i = 1; i <= n; i++) {
				u = v[i];
				for (p = adj[u]; p != NULL; p = p->next) {
					dp[0][k][p->id] = 0;
					dp[0][k][p->id ^ 1] = 0;
					dp[1][k][p->id] = 0;
					dp[1][k][p->id ^ 1] = 0;
				}
			}
			for (p = adj[s]; p != NULL; p = p->next) {
				dp[0][k][p->id ^ 1] = 0;
				dp[1][k][p->id ^ 1] = 0;
			}
		}
		for (p = adj[t]; p != NULL; p = p->next) dp[0][k_done][p->id] = p->label;
		for (l = 1, cur = 1, prev = 0; l <= n; l++, cur ^= 1, prev ^= 1) {
			for (p = adj[s], tmp = 0; p != NULL; p = p->next) if (flag[p->v] > -2) tmp ^= dp[prev][bit[K] - 1][p->id ^ 1];
			if (tmp != 0 || l == n) break;
			
			for (k = 0; k < bit[K]; k++) {
				if ((k & k_done) != k_done) continue;
				for (i = 1; i <= n; i++) {
					u = v[i];
					h = flag[u];
					if (u == s || u == t || (h >= 0 && (k & bit[h]) != 0)) continue;
					for (p = adj[u], tmp = 0; p != NULL; p = p->next) if (flag[p->v] > -2) tmp ^= dp[prev][k][p->id ^ 1];
					for (p = adj[u]; p != NULL; p = p->next) {
						if (h < 0) dp[cur][k][p->id] = nim_product(tmp, p->label);
						else dp[cur][k | bit[h]][p->id] = nim_product(tmp ^ dp[prev][k][p->id ^ 1], p->label);
						if (flag[p->v] > -2) dp[prev][k][p->id ^ 1] = 0;
					}
				}
			}
		}
		if (tmp != 0) {
			if (l < l_ans) {
				for (p = adj[s], l_ans = l, ans[0] = N + 1; p != NULL; p = p->next) if (flag[p->v] > -2 && dp[prev][bit[K] - 1][p->id ^ 1] != 0) chmin(&(ans[0]), p->v);
			} else if (l == l_ans) {
				for (p = adj[s]; p != NULL; p = p->next) if (flag[p->v] > -2 && dp[prev][bit[K] - 1][p->id ^ 1] != 0) chmin(&(ans[0]), p->v);
			}
		}
	}
	
	if (l_ans > n) {
		for (i = 0; i < n; i++) ans[i] = 0;
		return n + 1;
	} else if (l_ans == 1) {
		ans[0] = s;
		return 1;
	} else {
		if (flag[ans[0]] == -1) flag[ans[0]] = -2;
		else flag[ans[0]] = -3 - flag[ans[0]];
		return lexmin_shortest_path_through_specified_vertices(N, adj, e, ans[0], t, K, flag, &(ans[1]), rep) + 1;
	}
}

void solve(int N, int M, int X, int Y, int Z, int A[], int B[], int ans[])
{
	static int K = 2, T[K_MAX];
	static edge *adj[N_MAX + 1] = {}, e[M_MAX * 2];
	complement_graph(N, M, A, B, adj, e);
	T[0] = Y;
	T[1] = Z;
	
	static char flag[N_MAX + 1];
	static int i, u;
	for (u = 1; u <= N; u++) flag[u] = -1; // nonterminals
	for (i = 0; i < K; i++) flag[T[i]] = i; // terminals
	ans[0] = lexmin_shortest_path_through_specified_vertices(N, adj, e, X, X, K, flag, &(ans[2]), 2);
	if (ans[0] <= N) ans[1] = X;
}

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



int main()
{
	int i, N, M, X, Y, Z, A[M_MAX + 1], B[M_MAX + 1], ans[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]));
	solve(N, M, X, Y, Z, A, B, ans);
	print_ans(N, ans);
	fflush(stdout);
	return 0;
}
0