結果
| 問題 | No.2987 Colorful University of Tree |
| ユーザー |
👑  ygussany
|
| 提出日時 | 2024-12-12 02:19:44 |
| 言語 | C (gcc 13.3.0) |
| 結果 |
AC
|
| 実行時間 | 594 ms / 5,000 ms |
| コード長 | 8,558 bytes |
| コンパイル時間 | 518 ms |
| コンパイル使用メモリ | 39,136 KB |
| 実行使用メモリ | 52,304 KB |
| 最終ジャッジ日時 | 2024-12-12 02:20:03 |
| 合計ジャッジ時間 | 19,196 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 41 |
ソースコード
#include <stdio.h>#include <stdlib.h>#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;}void shuffle_permutation(int N, int p[], int K){int i, j;while (K--) {i = genrand() % N + 1;j = genrand() % N + 1;if (i != j) {p[i] ^= p[j];p[j] ^= p[i];p[i] ^= p[j];}}}void chmax(int *a, int b){if (*a < b) *a = b;}typedef struct {int key, id;} data;typedef struct {data obj[200001];int size;} max_heap;void push(max_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(max_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;}const int inf = -1;int leaf[200001];typedef struct {int left, right, max;} seg_node;void init_node(seg_node v[], int k, int l, int r){v[k].left = l;v[k].right = r;v[k].max = inf;if (l < r) {init_node(v, k << 1, l, (l + r) / 2);init_node(v, (k << 1) ^ 1, (l + r) / 2 + 1, r);} else leaf[l] = k;}void update_node(seg_node v[], int k, int x){int i, j = leaf[k];v[j].max = x;for (i = j >> 1; i > 0; j = i, i >>= 1) v[i].max = (v[j].max > v[j^1].max)? v[j].max: v[j^1].max;}int get_max(seg_node v[], int k, int l, int r){int tmp[2];if (v[k].right < l || v[k].left > r) return inf;else if (v[k].left >= l && v[k].right <= r) return v[k].max;else {tmp[0] = get_max(v, k << 1, l, r);tmp[1] = get_max(v, (k << 1) ^ 1, l, r);return (tmp[0] < tmp[1])? tmp[1]: tmp[0];}}int BS_left(seg_node v[], int k, int l, int r, int x){int tmp;if (v[k].max < x || v[k].right < l || v[k].left > r) return r + 1;else if (v[k].left == v[k].right) return v[k].left;else {tmp = BS_left(v, k << 1, l, r, x);if (tmp <= r) return tmp;else return BS_left(v, (k << 1) ^ 1, l, r, x);}}int bin_packing(int N, int deg[], int F[]){int u, Q;for (Q = 1; Q * Q < (N - 1) * 2; Q++);for (u = 1; u <= N; u++) chmax(&Q, deg[u]);if ((long long)(Q - 1) * (Q - 1) < (N - 1) * 2) {int i, j, k, u, q, max;static int dp[1001], num[1001], use[1001];for (i = 1; i <= Q; i++) num[i] = 0;for (u = 1; u <= N; u++) {F[u] = 0;num[deg[u]]++;}for (q = 1; q <= Q; q++) {for (i = 1; i <= Q; i++) if (num[i] > 0) break;if (i > Q) break;for (i = 1; i <= Q; i++) use[i] = 0;for (j = 1, dp[0] = 0; j <= Q; j++) dp[j] = -1;for (i = Q, max = 0; i >= 1 && max < Q; i--) {for (j = max; j >= 0; j--) {if (dp[j] < 0) continue;for (k = 1; k <= num[i] && j + i * k <= Q; k++) {if (dp[j+i*k] < 0) {dp[j+i*k] = i;chmax(&max, j + i * k);}}}}for (j = Q; dp[j] < 0; j--);while (j > 0) {use[dp[j]]++;j -= dp[j];}for (u = 1; u <= N; u++) {if (F[u] == 0 && use[deg[u]] > 0) {F[u] = q;use[deg[u]]--;num[deg[u]]--;}}}for (u = 1; u <= N; u++) if (F[u] == 0) break;if (u > N) return Q;Q++;for (i = 1; i <= Q; i++) num[i] = 0;for (u = 1; u <= N; u++) {F[u] = 0;num[deg[u]]++;}for (q = 1; q <= Q; q++) {for (i = 1; i <= Q; i++) if (num[i] > 0) break;if (i > Q) break;for (i = 1; i <= Q; i++) use[i] = 0;for (j = 1, dp[0] = 0; j <= Q; j++) dp[j] = -1;for (i = Q, max = 0; i >= 1 && max < Q; i--) {for (j = max; j >= 0; j--) {if (dp[j] < 0) continue;for (k = 1; k <= num[i] && j + i * k <= Q; k++) {if (dp[j+i*k] < 0) {dp[j+i*k] = i;chmax(&max, j + i * k);}}}}for (j = Q; dp[j] < 0; j--);while (j > 0) {use[dp[j]]++;j -= dp[j];}for (u = 1; u <= N; u++) {if (F[u] == 0 && use[deg[u]] > 0) {F[u] = q;use[deg[u]]--;num[deg[u]]--;}}}for (u = 1; u <= N; u++) if (F[u] == 0) exit(-1);return Q;}int i;static seg_node v[524288];init_node(v, 1, 1, Q);for (i = 1; i <= Q; i++) update_node(v, i, Q);static max_heap h;data d;h.size = 0;for (u = 1; u <= N; u++) {d.key = deg[u];d.id = u;push(&h, d);}while (h.size > 0) {d = pop(&h);u = d.id;i = BS_left(v, 1, 1, Q, deg[u]);F[u] = i;update_node(v, i, get_max(v, 1, i, i) - deg[u]);}return Q;}int solve(int N, int deg[], int *adj[], int F[], int *FF[]){int Q = bin_packing(N, deg, F);int i, u;static int ed[200001][2][2];for (i = 1; i <= N - 1; i++) ed[i][0][0] = 0;for (u = 1; u <= N; u++) {for (i = 1; i <= deg[u]; i++) {if (ed[adj[u][i]][0][0] == 0) {ed[adj[u][i]][0][0] = u;ed[adj[u][i]][0][1] = i;} else {ed[adj[u][i]][1][0] = u;ed[adj[u][i]][1][1] = i;}}}int j, k;static int p[200001], *q[200001], *qq[200001], num[200001];for (i = 1; i <= Q; i++) num[i] = 0;for (u = 1; u <= N; u++) num[F[u]] += deg[u];for (i = 1; i <= Q; i++) {q[i] = (int*)malloc(sizeof(int) * (num[i] + 1));qq[i] = (int*)malloc(sizeof(int) * (num[i] + 1));num[i] = 0;}for (u = 1; u <= N; u++) {for (i = 1; i <= deg[u]; i++) {q[F[u]][++num[F[u]]] = u;qq[F[u]][num[F[u]]] = i;}}for (i = 1; i <= Q; i++) p[i] = i;shuffle_permutation(Q, p, Q * 10);for (i = 1; i <= Q; i++) {shuffle_permutation(Q, p, 100);for (j = 1, k = genrand() % Q + 1; j <= num[i]; j++, k++) {if (k > Q) k -= Q;FF[q[i][j]][qq[i][j]] = p[k];}}int w, r, ww, jj;for (k = 1; k <= N - 1; k++) {u = ed[k][0][0];i = ed[k][0][1];w = ed[k][1][0];j = ed[k][1][1];while (FF[u][i] == FF[w][j]) {// printf("[%d %d %d %d]\n", u, i, w, j);if (num[F[w]] == 1) {FF[w][j]++;if (FF[w][j] > Q) FF[w][j] -= Q;} else {do {r = genrand() % num[F[w]] + 1;} while (q[F[w]][r] == w && qq[F[w]][r] == j);ww = q[F[w]][r];jj = qq[F[w]][r];FF[w][j] ^= FF[ww][jj];FF[ww][jj] ^= FF[w][j];FF[w][j] ^= FF[ww][jj];u = ww;i = jj;w = ed[adj[u][i]][0][0] ^ ed[adj[u][i]][1][0] ^ u;j = ed[adj[u][i]][0][1] ^ ed[adj[u][i]][1][1] ^ i;}}}for (i = 1; i <= Q; i++) {free(q[i]);free(qq[i]);}return Q;}int main(){int T, i, u, N, deg[200001], *adj[200001], F[200001], *FF[200001];scanf("%d", &T);while (T--) {scanf("%d", &N);for (u = 1; u <= N; u++) {scanf("%d", &(deg[u]));adj[u] = (int*)malloc(sizeof(int) * (deg[u] + 1));FF[u] = (int*)malloc(sizeof(int) * (deg[u] + 1));for (i = 1; i <= deg[u]; i++) {scanf("%d", &(adj[u][i]));}}printf("%d\n", solve(N, deg, adj, F, FF));for (u = 1; u <= N; u++) {printf("%d", F[u]);for (i = 1; i <= deg[u]; i++) printf(" %d", FF[u][i]);printf("\n");}for (u = 1; u <= N; u++) {free(adj[u]);free(FF[u]);}}/*scanf("%d", &N);while (1) {for (u = 1; u <= N; u++) deg[u] = 0;for (u = 2; u <= N; u++) {deg[u]++;deg[genrand() % (u - 1) + 1]++;}bin_packing(N, deg, F);printf("a");}*/fflush(stdout);return 0;}