結果
| 問題 | 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 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;
}
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;
}