結果
| 問題 |
No.1776 Love Triangle 2 (Hard)
|
| ユーザー |
👑  ygussany
|
| 提出日時 | 2021-11-19 18:40:20 |
| 言語 | C (gcc 13.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 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 176 |
ソースコード
#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;
}