結果

問題 No.2985 May Count Induced C4 Subgraphs
ユーザー 👑 ygussany
提出日時 2024-12-10 22:25:31
言語 C
(gcc 13.3.0)
結果
TLE  
実行時間 -
コード長 8,204 bytes
コンパイル時間 672 ms
コンパイル使用メモリ 38,204 KB
実行使用メモリ 120,704 KB
最終ジャッジ日時 2024-12-10 22:26:28
合計ジャッジ時間 56,764 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 16 TLE * 6
権限があれば一括ダウンロードができます

ソースコード

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

#include <stdio.h>
const int Mod = 998244353;
typedef struct HList {
    struct HList *next;
    int u, w;
} hlist;
#define HASH 5000011
const int H_Mod = HASH;
int hash_func(int u, int w)
{
    return (((long long)u << 30) + w) % H_Mod;
}
int hn = 0;
hlist *hash[HASH] = {}, hd[200001];
int is_adjacent(int u, int w)
{
    if (u > w) {
        u ^= w;
        w ^= u;
        u ^= w;
    }
    
    int h;
    hlist *hp;
    h = hash_func(u, w);
    for (hp = hash[h]; hp != NULL; hp = hp->next) if (hp->u == u && hp->w == w) return 1;
    return 0;
}
typedef struct Edge {
    struct Edge *next;
    int v;
} edge;
typedef struct {
    int key, id;
} data;
typedef struct {
    data obj[400001];
    int size;
} min_heap;
void push(min_heap* h, data x)
{
    int i = ++(h->size), j = i >> 1;
    data tmp;
    h->obj[i] = x;
    while (j > 0) {
        if (h->obj[i].key < h->obj[j].key) {
            tmp = h->obj[j];
            h->obj[j] = h->obj[i];
            h->obj[i] = tmp;
            i = j;
            j >>= 1;
        } else break;
    }
}
data pop(min_heap* h)
{
    int i = 1, j = 2;
    data output = h->obj[1], tmp;
    h->obj[1] = h->obj[(h->size)--];
    while (j <= h->size) {
        if (j < h->size && h->obj[j^1].key < h->obj[j].key) j ^= 1;
        if (h->obj[j].key < h->obj[i].key) {
            tmp = h->obj[j];
            h->obj[j] = h->obj[i];
            h->obj[i] = tmp;
            i = j;
            j <<= 1;
        } else break;
    }
    return output;
}
void count_triangles_sub(int n, int v[], long long *num_edge, long long *num_triangle)
{
    int h, i, j, k;
    static int adj_mat[1001][1001] = {}, q[200001][2];
    for (i = 1, *num_edge = 0; i <= n; i++) {
        for (j = i + 1; j <= n; j++) {
            if (is_adjacent(v[i], v[j]) != 0) {
                adj_mat[i][j] = 1;
                adj_mat[j][i] = 1;
                q[++(*num_edge)][0] = i;
                q[*num_edge][1] = j;
            }
        }
    }
    if (*num_edge == n * (n - 1) / 2) *num_triangle = n * (n - 1) * (n - 2) / 6;
    else if (*num_edge == n * (n - 1) / 2 - 1) *num_triangle = n * (n - 1) * (n - 2) / 6 - (n - 2);
    else {
        for (h = 1, *num_triangle = 0; h <= *num_edge; h++) {
            i = q[h][0];
            j = q[h][1];
            for (k = 1; k <= n; k++) *num_triangle += adj_mat[i][k] & adj_mat[j][k];
        }
        *num_triangle /= 3;
    }
    for (i = 1; i <= n; i++) for (j = i + 1; j <= n; j++) { adj_mat[i][j] = 0; adj_mat[j][i] = 0; }
}
int solve(int N, int M, int U[], int V[])
{
    int i;
    for (i = 1; i <= M; i++) {
        if (U[i] > V[i]) {
            U[i] ^= V[i];
            V[i] ^= U[i];
            U[i] ^= V[i];
        }
    }
    if (N <= 3) return 0;
    
    int h, u, w;
    static int ed[200001][2];
    for (i = 1, hn = 0; i <= M; i++) {
        u = U[i];
        w = V[i];
        ed[i][0] = u;
        ed[i][1] = w;
        h = hash_func(u, w);
        hd[hn].u = u;
        hd[hn].w = w;
        hd[hn].next = hash[h];
        hash[h] = &(hd[hn++]);
    }
    
    static int deg[200001];
    static edge *adj[200001], e[400001], *ep;
    for (u = 1; u <= N; u++) {
        deg[u] = 0;
        adj[u] = NULL;
    }
    for (i = 1; i <= M; i++) {
        u = ed[i][0];
        w = ed[i][1];
        e[i*2-1].v = w;
        e[i*2-1].next = adj[u];
        adj[u] = &(e[i*2-1]);
        e[i*2].v = u;
        e[i*2].next = adj[w];
        adj[w] = &(e[i*2]);
        deg[u]++;
        deg[w]++;
    }
    
    int r, j, tail;
    static int flag[200001], q[200001];
    long long ans, tmp;
    ans = (__int128)N * (N - 1) * (N - 2) * (N - 3) / 24 % Mod;
    ans += Mod - (long long)M * (N - 2) * (N - 3) / 2 % Mod;
    for (u = 1, tmp = (long long)M * (M - 1) / 2; u <= N; u++) {
        flag[u] = 0;
        tmp -= (long long)deg[u] * (deg[u] - 1) / 2;
        ans += (long long)deg[u] * (deg[u] - 1) / 2 * (N - 3) % Mod;
        ans += Mod - (long long)deg[u] * (deg[u] - 1) * (deg[u] - 2) / 6 % Mod;
    }
    ans += tmp;
    for (i = 1; i <= M; i++) {
        u = ed[i][0];
        w = ed[i][1];
        ans += Mod - (long long)(deg[u] - 1) * (deg[w] - 1) % Mod;
    }
    for (u = 1; u <= N; u++) {
        for (ep = adj[u], tail = 0; ep != NULL; ep = ep->next) {
            w = ep->v;
            flag[w] = 1;
            q[++tail] = w;
        }
        if (tail >= 3) {
            if (tail <= 500) {
                for (i = 1, tmp = 0; i <= tail; i++) for (j = i + 1; j <= tail; j++) tmp += is_adjacent(q[i], q[j]);
            } else {
                for (i = 1, tmp = 0; i <= M; i++) if (flag[ed[i][0]] != 0 && flag[ed[i][1]] != 0) tmp++;
            }
            ans += tmp * (tail - 2) % Mod;
        }
        for (i = 1; i <= tail; i++) flag[q[i]] = 0;
    }
    
    int n = N;
    long long num_triangle = 0, tmp_num_edge, tmp_num_triangle;
    static min_heap he;
    data d;
    he.size = 0;
    for (u = 1; u <= N; u++) {
        d.key = deg[u];
        d.id = u;
        push(&he, d);
    }
    while (he.size > 0) {
        d = pop(&he);
        u = d.id;
        if (flag[u] != 0) continue;
        flag[u] = 1;
        n--;
        if (deg[u] == n) {
            num_triangle += (n + 1) * n * (n - 1) / 6;
            ans += Mod - (long long)(n + 1) * n * (n - 1) * (n - 2) / 24 * 2 % Mod;
            break;
        }
        for (ep = adj[u], tail = 0; ep != NULL; ep = ep->next) {
            w = ep->v;
            if (flag[w] == 0) {
                q[++tail] = w;
                deg[w]--;
                d.key = deg[w];
                d.id = w;
                push(&he, d);
            }
        }
        // for (i = 1; i <= tail; i++) for (j = i + 1; j <= tail; j++) num_triangle += is_adjacent(q[i], q[j]);
        count_triangles_sub(tail, q, &tmp_num_edge, &tmp_num_triangle);
        num_triangle += tmp_num_edge;
        if (tail >= 3) ans += Mod - tmp_num_triangle * 2 % Mod;
    }
    ans += num_triangle * 3;
    ans += Mod - num_triangle * (N - 3) % Mod;
    for (i = 1; i <= M; i++) {
        u = ed[i][0];
        w = ed[i][1];
        h = hash_func(u, w);
        hash[h] = NULL;
    }
    return ans % Mod;
}
int naive(int N, int M, int U[], int V[])
{
    int i, u, w;
    static int adj[101][101] = {};
    for (i = 1; i <= M; i++) {
        u = U[i];
        w = V[i];
        adj[u][w] = 1;
        adj[w][u] = 1;
    }
    
    int x, y, ans = 0;
    for (u = 1; u <= N; u++) {
        for (w = u + 1; w <= N; w++) {
            for (x = w + 1; x <= N; x++) {
                for (y = x + 1; y <= N; y++) {
                    if (adj[u][w] == 0 && adj[u][x] == 0 && adj[u][y] == 0 && adj[w][x] == 0 && adj[w][y] == 0 && adj[x][y] == 0) ans++;
                    else if (adj[u][w] == 1 && adj[u][x] == 1 && adj[u][y] == 0 && adj[w][x] == 0 && adj[w][y] == 1 && adj[x][y] == 1) ans--;
                    else if (adj[u][w] == 1 && adj[u][x] == 0 && adj[u][y] == 1 && adj[w][x] == 1 && adj[w][y] == 0 && adj[x][y] == 1) ans--;
                    else if (adj[u][w] == 0 && adj[u][x] == 1 && adj[u][y] == 1 && adj[w][x] == 1 && adj[w][y] == 1 && adj[x][y] == 0) ans--;
                }
            }
        }
    }
    for (i = 1; i <= M; i++) {
        u = U[i];
        w = V[i];
        adj[u][w] = 0;
        adj[w][u] = 0;
    }
    if (ans < 0) ans += Mod;
    return ans;
}
#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;
}
int main()
{
    int i, N, M, U[200001], V[200001];
    scanf("%d %d", &N, &M);
    for (i = 1; i <= M; i++) scanf("%d %d", &(U[i]), &(V[i]));
    printf("%d %d\n", Mod - 1, solve(N, M, U, V));
    
    /*
    int u, w, ans[2], adj_mat[101][101];
    while (1) {
        for (u = 1; u <= N; u++) for (w = 1; w <= N; w++) adj_mat[u][w] = 0;
        for (u = 1, M = 0; u <= N; u++) {
            for (w = u + 1; w <= N; w++) {
                adj_mat[u][w] = genrand() % 2;
                adj_mat[w][u] = adj_mat[u][w];
                if (adj_mat[u][w] == 1) {
                    U[++M] = u;
                    V[M] = w;
                }
            }
        }
        ans[0] = naive(N, M, U, V);
        ans[1] = naive(N, M, U, V);
        printf("[%d %d]\n", ans[0], ans[1]);
        fflush(stdout);
        if (ans[0] != ans[1]) {
            for (i = 1; i <= M; i++) printf("%d %d\n", U[i], V[i]);
            printf("[%d %d]\n", ans[0], ans[1]);
            break;
        }
    }
    */
    fflush(stdout);
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0