結果

問題 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0