結果
| 問題 | No.2985 May Count Induced C4 Subgraphs |
| ユーザー |
👑  ygussany
|
| 提出日時 | 2024-12-10 17:43:21 |
| 言語 | C (gcc 13.3.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 4,712 bytes |
| コンパイル時間 | 790 ms |
| コンパイル使用メモリ | 36,096 KB |
| 実行使用メモリ | 119,424 KB |
| 最終ジャッジ日時 | 2024-12-10 17:44:13 |
| 合計ジャッジ時間 | 49,209 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 10 WA * 7 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 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]));if (U[i] > V[i]) {U[i] ^= V[i];V[i] ^= U[i];U[i] ^= V[i];}}if (N <= 3) {printf("0 0\n");return 0;}int h, u, w, ed[200001][2];for (i = 1; 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++]);}int deg[200001] = {};edge *adj[200001] = {}, e[400001], *ep;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, flag[200001] = {}, q[200001], j, tail;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++) {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; 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;}}long long num_triangle = 0, tmp_num_edge, tmp_num_triangle;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;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 += tmp_num_edge * (tail - 2) % Mod;ans += Mod - tmp_num_triangle * 2 % Mod;}}ans += num_triangle * 3;ans += Mod - num_triangle * (N - 3) % Mod;printf("%d %lld\n", Mod - 1, ans % Mod);fflush(stdout);return 0;}