結果

問題 No.2981 Pack Tree into Grid
ユーザー 👑 ygussany
提出日時 2024-12-05 00:58:08
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 6 ms / 2,000 ms
コード長 4,356 bytes
コンパイル時間 1,753 ms
コンパイル使用メモリ 33,840 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-12-05 00:58:12
合計ジャッジ時間 2,393 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>

typedef struct Edge {
	struct Edge *next;
	int v, flag;
} edge;

int next_permutation(int n, int p[])
{
	int i, head, tail = 0;
	static int q[5];
	for (i = n - 1, q[tail++] = p[n]; i >= 1; i--) {
		if (p[i] >= p[i+1]) q[tail++] = p[i];
		else break;
	}
	if (i == 0) return 0;
	
	int l = 0, r = tail - 1, m;
	while (l < r) {
		m = (l + r) / 2;
		if (q[m] <= p[i]) l = m + 1;
		else r = m;
	}
	p[i] ^= q[l];
	q[l] ^= p[i];
	p[i] ^= q[l];
	for (i++, head = 0; i <= n; i++, head++) p[i] = q[head];
	return 1;
}

int tree_isomorphism(int r, edge *adj[], int rr, edge *adjj[], int ans[])
{
	int n = 0, nn = 0, q[5], qq[5];
	edge *p, *pp;
	for (p = adj[r]; p != NULL; p = p->next) if (p->flag != 0) q[++n] = p->v;
	for (pp = adjj[rr]; pp != NULL; pp = pp->next) if (pp->flag != 0) qq[++nn] = pp->v;
	
	if (n == 0 && nn == 0) {
		ans[r] = rr;
		return 1;
	} else if (n != nn) return 0;
	
	int i, perm[5];
	for (i = 1; i <= n; i++) perm[i] = i;
	for (i = 1; i <= n; i++) {
		for (p = adj[q[i]]; p != NULL; p = p->next) if (p->v == r) p->flag = 0;
		for (pp = adjj[qq[i]]; pp != NULL; pp = pp->next) if (pp->v == rr) pp->flag = 0;
	}
	do {
		for (i = 1; i <= n; i++) if (tree_isomorphism(q[i], adj, qq[perm[i]], adjj, ans) == 0) break;
		if (i > n) {
			for (i = 1; i <= n; i++) {
				for (p = adj[q[i]]; p != NULL; p = p->next) if (p->v == r) p->flag = 1;
				for (pp = adjj[qq[i]]; pp != NULL; pp = pp->next) if (pp->v == rr) pp->flag = 1;
			}
			ans[r] = rr;
			return 1;
		}
	} while (next_permutation(n, perm));
	for (i = 1; i <= n; i++) {
		for (p = adj[q[i]]; p != NULL; p = p->next) if (p->v == r) p->flag = 1;
		for (pp = adjj[qq[i]]; pp != NULL; pp = pp->next) if (pp->v == rr) pp->flag = 1;
	}
	return 0;
}

int solve(int N, int a[], int b[], int c[], int H, int W, char S[][27], int ans[][2])
{
	int i, j, u, w, n = 0, m = 0, v[14][27], v_inv[301][2];
	static edge *adj[2][301], e[2][601];
	for (i = 1; i <= H; i++) {
		for (j = 1; j <= W; j++) {
			if (S[i][j] == '#') {
				v[i][j] = ++n;
				v_inv[n][0] = i;
				v_inv[n][1] = j;
			} else v[i][j] = 0;
		}
	}
	for (i = 1; i <= n; i++) {
		adj[0][i] = NULL;
		adj[1][i] = NULL;
	}
	for (i = 1; i <= H; i++) {
		for (j = 1; j <= W; j++) {
			if (S[i][j] != '#') continue;
			if (S[i+1][j] == '#') {
				u = v[i][j];
				w = v[i+1][j];
				e[0][m].v = w;
				e[0][m].flag = 1;
				e[0][m].next = adj[0][u];
				adj[0][u] = &(e[0][m++]);
				e[0][m].v = u;
				e[0][m].flag = 1;
				e[0][m].next = adj[0][w];
				adj[0][w] = &(e[0][m++]);
			}
			if (S[i][j+1] == '#') {
				u = v[i][j];
				w = v[i][j+1];
				e[0][m].v = w;
				e[0][m].flag = 1;
				e[0][m].next = adj[0][u];
				adj[0][u] = &(e[0][m++]);
				e[0][m].v = u;
				e[0][m].flag = 1;
				e[0][m].next = adj[0][w];
				adj[0][w] = &(e[0][m++]);
			}
		}
	}
	
	int sum = 0;
	static int deg[301];
	for (i = 1; i <= N - 1; i++) sum += c[i];
	if (sum != n - 1) return 0;
	for (i = 1; i <= n; i++) deg[i] = 0;
	for (i = 1, n = N, m = 0; i <= N - 1; i++) {
		u = a[i];
		while (c[i] > 1) {
			c[i]--;
			w = ++n;
			e[1][m].v = w;
			e[1][m].flag = 1;
			e[1][m].next = adj[1][u];
			adj[1][u] = &(e[1][m++]);
			e[1][m].v = u;
			e[1][m].flag = 1;
			e[1][m].next = adj[1][w];
			adj[1][w] = &(e[1][m++]);
			deg[u]++;
			deg[w]++;
			u = w;
		}
		w = b[i];
		e[1][m].v = w;
		e[1][m].flag = 1;
		e[1][m].next = adj[1][u];
		adj[1][u] = &(e[1][m++]);
		e[1][m].v = u;
		e[1][m].flag = 1;
		e[1][m].next = adj[1][w];
		adj[1][w] = &(e[1][m++]);
		deg[u]++;
		deg[w]++;
	}
	for (i = 1; i <= n; i++) if (deg[i] > 4) return 0;
	
	int perm[301];
	for (i = 1; i <= n; i++) if (tree_isomorphism(1, adj[1], i, adj[0], perm) != 0) break;
	if (i > n) return 0;
	for (i = 1; i <= N; i++) {
		ans[i][0] = v_inv[perm[i]][0];
		ans[i][1] = v_inv[perm[i]][1];
	}
	return 1;
}

int main()
{
	int T, N, u[301], v[301], w[301], i, j, H, W, ans[301][2];
	char S[14][27];
	scanf("%d", &T);
	while (T--) {
		scanf("%d", &N);
		for (i = 1; i <= N - 1; i++) scanf("%d %d %d", &(u[i]), &(v[i]), &(w[i]));
		scanf("%d %d", &H, &W);
		for (i = 0; i <= H + 1; i++) for (j = 0; j <= W + 1; j++) S[i][j] = 0;
		for (i = 1; i <= H; i++) scanf("%s", &(S[i][1]));
		if (solve(N, u, v, w, H, W, S, ans) != 0) {
			printf("Yes\n");
			for (i = 1; i <= N; i++) printf("%d %d\n", ans[i][0], ans[i][1]);
		} else printf("No\n");
	}
	fflush(stdout);
	return 0;
}
0