結果
| 問題 | No.1775 Love Triangle 2 |
| ユーザー |
👑  ygussany
|
| 提出日時 | 2021-11-19 23:53:34 |
| 言語 | C (gcc 13.3.0) |
| 結果 |
AC
|
| 実行時間 | 2,316 ms / 8,000 ms |
| コード長 | 5,906 bytes |
| コンパイル時間 | 590 ms |
| コンパイル使用メモリ | 36,080 KB |
| 実行使用メモリ | 18,560 KB |
| 最終ジャッジ日時 | 2024-07-04 17:19:06 |
| 合計ジャッジ時間 | 10,406 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 90 |
ソースコード
#include <stdio.h>#define N_MAX 100#define M_MAX 5000typedef 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 0x7fffffffULstatic 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^32const 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 additionunsigned 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 skipping terminals)int solve4_3(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 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 k, kk, l, x, y, z;static unsigned int dp[N_MAX + 1][4][N_MAX + 1][N_MAX + 1], tmp;for (l = 1; l <= N; l++) {for (k = 0; k < 4; k++) {for (p = adj[X]; p != NULL; p = p->next) {for (u = 1; u <= N; u++) dp[l][k][p->v][u] = 0;}}}for (p = adj[X]; p != NULL; p = p->next) {u = p->v;dp[1][0][u][u] = p->label;}for (l = 1; l <= N; l++) {for (p = adj[X]; p != NULL; p = p->next) {for (pp = p->next; pp != NULL; pp = pp->next) if (dp[l][3][p->v][pp->v] != 0) return l + 1;}if (l == N) return -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++) {if (y == X || y == Y || y == Z) continue;tmp = dp[l][k][w][y];for (pp = adj[y]; pp != NULL; pp = pp->next) {z = pp->v;dp[l+1][k][w][z] ^= nim_product(tmp, pp->label);}if (l == N - 1) continue;if ((k & 1) == 0) {for (pp = d_adj[1][y]; pp != NULL; pp = pp->next) {z = pp->v;dp[l+2][k|1][w][z] ^= nim_product(tmp, pp->label);}}if ((k & 2) == 0) {for (pp = d_adj[2][y]; pp != NULL; pp = pp->next) {z = pp->v;dp[l+2][k|2][w][z] ^= nim_product(tmp, pp->label);}}}}}}}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_3(N, M, X, Y, Z, A, B);// ans[1] = solve4_3(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;}