結果
問題 | No.1776 Love Triangle 2 (Hard) |
ユーザー | 👑 ygussany |
提出日時 | 2021-11-24 13:15:17 |
言語 | C (gcc 12.3.0) |
結果 |
AC
|
実行時間 | 2,836 ms / 10,000 ms |
コード長 | 7,608 bytes |
コンパイル時間 | 875 ms |
コンパイル使用メモリ | 36,252 KB |
実行使用メモリ | 4,384 KB |
最終ジャッジ日時 | 2023-09-21 02:33:08 |
合計ジャッジ時間 | 64,549 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,380 KB |
testcase_01 | AC | 1 ms
4,380 KB |
testcase_02 | AC | 1 ms
4,380 KB |
testcase_03 | AC | 1 ms
4,376 KB |
testcase_04 | AC | 317 ms
4,376 KB |
testcase_05 | AC | 393 ms
4,376 KB |
testcase_06 | AC | 396 ms
4,380 KB |
testcase_07 | AC | 135 ms
4,380 KB |
testcase_08 | AC | 379 ms
4,380 KB |
testcase_09 | AC | 12 ms
4,380 KB |
testcase_10 | AC | 20 ms
4,376 KB |
testcase_11 | AC | 12 ms
4,380 KB |
testcase_12 | AC | 10 ms
4,376 KB |
testcase_13 | AC | 11 ms
4,376 KB |
testcase_14 | AC | 12 ms
4,376 KB |
testcase_15 | AC | 15 ms
4,376 KB |
testcase_16 | AC | 13 ms
4,380 KB |
testcase_17 | AC | 15 ms
4,376 KB |
testcase_18 | AC | 29 ms
4,376 KB |
testcase_19 | AC | 14 ms
4,380 KB |
testcase_20 | AC | 16 ms
4,376 KB |
testcase_21 | AC | 13 ms
4,380 KB |
testcase_22 | AC | 13 ms
4,380 KB |
testcase_23 | AC | 10 ms
4,376 KB |
testcase_24 | AC | 12 ms
4,376 KB |
testcase_25 | AC | 12 ms
4,376 KB |
testcase_26 | AC | 13 ms
4,376 KB |
testcase_27 | AC | 12 ms
4,380 KB |
testcase_28 | AC | 13 ms
4,380 KB |
testcase_29 | AC | 37 ms
4,376 KB |
testcase_30 | AC | 99 ms
4,380 KB |
testcase_31 | AC | 296 ms
4,376 KB |
testcase_32 | AC | 474 ms
4,380 KB |
testcase_33 | AC | 594 ms
4,376 KB |
testcase_34 | AC | 593 ms
4,376 KB |
testcase_35 | AC | 566 ms
4,380 KB |
testcase_36 | AC | 444 ms
4,376 KB |
testcase_37 | AC | 270 ms
4,376 KB |
testcase_38 | AC | 57 ms
4,376 KB |
testcase_39 | AC | 57 ms
4,380 KB |
testcase_40 | AC | 185 ms
4,376 KB |
testcase_41 | AC | 279 ms
4,376 KB |
testcase_42 | AC | 289 ms
4,380 KB |
testcase_43 | AC | 235 ms
4,380 KB |
testcase_44 | AC | 89 ms
4,376 KB |
testcase_45 | AC | 600 ms
4,380 KB |
testcase_46 | AC | 120 ms
4,380 KB |
testcase_47 | AC | 13 ms
4,376 KB |
testcase_48 | AC | 52 ms
4,380 KB |
testcase_49 | AC | 25 ms
4,376 KB |
testcase_50 | AC | 89 ms
4,376 KB |
testcase_51 | AC | 255 ms
4,376 KB |
testcase_52 | AC | 422 ms
4,380 KB |
testcase_53 | AC | 506 ms
4,380 KB |
testcase_54 | AC | 508 ms
4,376 KB |
testcase_55 | AC | 489 ms
4,380 KB |
testcase_56 | AC | 457 ms
4,380 KB |
testcase_57 | AC | 238 ms
4,376 KB |
testcase_58 | AC | 178 ms
4,380 KB |
testcase_59 | AC | 62 ms
4,380 KB |
testcase_60 | AC | 131 ms
4,376 KB |
testcase_61 | AC | 175 ms
4,380 KB |
testcase_62 | AC | 71 ms
4,380 KB |
testcase_63 | AC | 66 ms
4,376 KB |
testcase_64 | AC | 106 ms
4,376 KB |
testcase_65 | AC | 15 ms
4,376 KB |
testcase_66 | AC | 30 ms
4,380 KB |
testcase_67 | AC | 35 ms
4,380 KB |
testcase_68 | AC | 10 ms
4,376 KB |
testcase_69 | AC | 1,142 ms
4,376 KB |
testcase_70 | AC | 1,396 ms
4,380 KB |
testcase_71 | AC | 1,396 ms
4,380 KB |
testcase_72 | AC | 454 ms
4,376 KB |
testcase_73 | AC | 1,359 ms
4,376 KB |
testcase_74 | AC | 25 ms
4,376 KB |
testcase_75 | AC | 19 ms
4,380 KB |
testcase_76 | AC | 18 ms
4,376 KB |
testcase_77 | AC | 17 ms
4,376 KB |
testcase_78 | AC | 18 ms
4,380 KB |
testcase_79 | AC | 18 ms
4,380 KB |
testcase_80 | AC | 23 ms
4,376 KB |
testcase_81 | AC | 23 ms
4,380 KB |
testcase_82 | AC | 31 ms
4,376 KB |
testcase_83 | AC | 66 ms
4,376 KB |
testcase_84 | AC | 27 ms
4,376 KB |
testcase_85 | AC | 23 ms
4,380 KB |
testcase_86 | AC | 18 ms
4,376 KB |
testcase_87 | AC | 18 ms
4,376 KB |
testcase_88 | AC | 22 ms
4,380 KB |
testcase_89 | AC | 24 ms
4,376 KB |
testcase_90 | AC | 17 ms
4,380 KB |
testcase_91 | AC | 19 ms
4,380 KB |
testcase_92 | AC | 20 ms
4,380 KB |
testcase_93 | AC | 22 ms
4,380 KB |
testcase_94 | AC | 86 ms
4,380 KB |
testcase_95 | AC | 377 ms
4,376 KB |
testcase_96 | AC | 1,183 ms
4,376 KB |
testcase_97 | AC | 2,266 ms
4,380 KB |
testcase_98 | AC | 2,836 ms
4,380 KB |
testcase_99 | AC | 2,823 ms
4,376 KB |
testcase_100 | AC | 2,423 ms
4,376 KB |
testcase_101 | AC | 1,470 ms
4,380 KB |
testcase_102 | AC | 751 ms
4,380 KB |
testcase_103 | AC | 180 ms
4,376 KB |
testcase_104 | AC | 120 ms
4,376 KB |
testcase_105 | AC | 422 ms
4,380 KB |
testcase_106 | AC | 876 ms
4,376 KB |
testcase_107 | AC | 178 ms
4,380 KB |
testcase_108 | AC | 730 ms
4,376 KB |
testcase_109 | AC | 197 ms
4,380 KB |
testcase_110 | AC | 153 ms
4,380 KB |
testcase_111 | AC | 130 ms
4,376 KB |
testcase_112 | AC | 43 ms
4,376 KB |
testcase_113 | AC | 56 ms
4,376 KB |
testcase_114 | AC | 86 ms
4,380 KB |
testcase_115 | AC | 333 ms
4,376 KB |
testcase_116 | AC | 1,049 ms
4,376 KB |
testcase_117 | AC | 1,936 ms
4,380 KB |
testcase_118 | AC | 2,455 ms
4,376 KB |
testcase_119 | AC | 2,445 ms
4,376 KB |
testcase_120 | AC | 2,123 ms
4,380 KB |
testcase_121 | AC | 1,247 ms
4,376 KB |
testcase_122 | AC | 866 ms
4,376 KB |
testcase_123 | AC | 669 ms
4,376 KB |
testcase_124 | AC | 188 ms
4,380 KB |
testcase_125 | AC | 180 ms
4,380 KB |
testcase_126 | AC | 286 ms
4,380 KB |
testcase_127 | AC | 162 ms
4,380 KB |
testcase_128 | AC | 127 ms
4,376 KB |
testcase_129 | AC | 96 ms
4,380 KB |
testcase_130 | AC | 103 ms
4,376 KB |
testcase_131 | AC | 84 ms
4,380 KB |
testcase_132 | AC | 63 ms
4,376 KB |
testcase_133 | AC | 32 ms
4,376 KB |
testcase_134 | AC | 23 ms
4,380 KB |
testcase_135 | AC | 85 ms
4,376 KB |
testcase_136 | AC | 84 ms
4,376 KB |
testcase_137 | AC | 80 ms
4,380 KB |
testcase_138 | AC | 109 ms
4,380 KB |
testcase_139 | AC | 172 ms
4,376 KB |
testcase_140 | AC | 140 ms
4,376 KB |
testcase_141 | AC | 86 ms
4,376 KB |
testcase_142 | AC | 144 ms
4,376 KB |
testcase_143 | AC | 102 ms
4,380 KB |
testcase_144 | AC | 27 ms
4,376 KB |
testcase_145 | AC | 30 ms
4,376 KB |
testcase_146 | AC | 73 ms
4,380 KB |
testcase_147 | AC | 30 ms
4,376 KB |
testcase_148 | AC | 67 ms
4,380 KB |
testcase_149 | AC | 54 ms
4,380 KB |
testcase_150 | AC | 80 ms
4,376 KB |
testcase_151 | AC | 35 ms
4,384 KB |
testcase_152 | AC | 64 ms
4,380 KB |
testcase_153 | AC | 97 ms
4,376 KB |
testcase_154 | AC | 51 ms
4,380 KB |
testcase_155 | AC | 245 ms
4,376 KB |
testcase_156 | AC | 324 ms
4,376 KB |
testcase_157 | AC | 188 ms
4,380 KB |
testcase_158 | AC | 210 ms
4,376 KB |
testcase_159 | AC | 262 ms
4,376 KB |
testcase_160 | AC | 109 ms
4,376 KB |
testcase_161 | AC | 166 ms
4,380 KB |
testcase_162 | AC | 416 ms
4,376 KB |
testcase_163 | AC | 466 ms
4,380 KB |
testcase_164 | AC | 459 ms
4,380 KB |
testcase_165 | AC | 238 ms
4,380 KB |
testcase_166 | AC | 120 ms
4,376 KB |
testcase_167 | AC | 139 ms
4,376 KB |
testcase_168 | AC | 78 ms
4,376 KB |
testcase_169 | AC | 134 ms
4,376 KB |
testcase_170 | AC | 213 ms
4,380 KB |
testcase_171 | AC | 334 ms
4,380 KB |
testcase_172 | AC | 177 ms
4,376 KB |
testcase_173 | AC | 476 ms
4,376 KB |
testcase_174 | AC | 189 ms
4,376 KB |
testcase_175 | AC | 183 ms
4,380 KB |
ソースコード
#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; }