結果
| 問題 | No.2985 May Count Induced C4 Subgraphs |
| ユーザー |
👑  ygussany
|
| 提出日時 | 2024-12-10 22:13:13 |
| 言語 | C (gcc 13.3.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 8,066 bytes |
| コンパイル時間 | 1,498 ms |
| コンパイル使用メモリ | 38,440 KB |
| 実行使用メモリ | 60,416 KB |
| 最終ジャッジ日時 | 2024-12-10 22:13:56 |
| 合計ジャッジ時間 | 38,109 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 6 WA * 11 TLE * 5 |
ソースコード
#include <stdio.h>const int Mod = 998244353;typedef struct HList {struct HList *next;int u, w;} hlist;#define HASH 5000011const 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 i, j, k;static int adj_mat[1001][1001] = {};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; (*num_edge)++; }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 (i = 1, *num_triangle = 0; i <= n; i++) for (j = i + 1; j <= n; j++) for (k = j + 1; k <= n; k++) *num_triangle += adj_mat[i][j] &adj_mat[i][k] & adj_mat[j][k];}for (i = 1; i <= n; i++) for (j = i + 1; j <= n; j++) adj_mat[i][j] = 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 (n <= 500) return ans % Mod;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]);if (tail >= 3) {count_triangles_sub(tail, q, &tmp_num_edge, &tmp_num_triangle);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 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;}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;}