結果

問題 No.1775 Love Triangle 2
ユーザー 👑 ygussany
提出日時 2021-11-19 23:50:58
言語 C
(gcc 13.3.0)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 5,214 bytes
コンパイル時間 328 ms
コンパイル使用メモリ 35,820 KB
実行使用メモリ 41,048 KB
最終ジャッジ日時 2024-07-03 21:08:13
合計ジャッジ時間 9,838 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 4 TLE * 1 -- * 85
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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^5) time)
int solve5(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, *ppp;
    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 (x = 1; x <= N; x++) {
                    for (pp = adj[x]; pp != NULL; pp = pp->next) {
                        y = pp->v;
                        if (dp[prev][k][w][x][y] == 0) continue;
                        tmp = dp[prev][k][w][x][y];
                        dp[prev][k][w][x][y] = 0;
            
                        for (ppp = adj[y]; ppp != NULL; ppp = ppp->next) {
                            z = ppp->v;
                            kk = k | ((z == Y)? 1: (z == Z)? 2: 0);
                            if (((y == X || y == Y || y == Z) && z == x) || (z == X && kk != 3) || (z == Y && (k & 1) != 0) || (z == Z && (k & 2) != 
                                0)) continue;
                            dp[cur][kk][w][y][z] ^= nim_product(tmp, ppp->label);
                        }
                    }
                }
            }
        }
        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] = solve5(N, M, X, Y, Z, A, B);
    // ans[1] = solve5(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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0