結果

問題 No.2981 Pack Tree into Grid
コンテスト
ユーザー rin204
提出日時 2024-12-05 01:00:54
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 290 ms / 2,000 ms
コード長 9,047 bytes
コンパイル時間 3,790 ms
コンパイル使用メモリ 282,128 KB
実行使用メモリ 11,188 KB
最終ジャッジ日時 2024-12-05 01:01:01
合計ジャッジ時間 6,685 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

struct RandomNumberGenerator {
    std::mt19937 mt;
    RandomNumberGenerator() : mt(std::chrono::steady_clock::now().time_since_epoch().count()) {}
    RandomNumberGenerator(int seed) : mt(seed) {}

    int operator()(int a, int b) {
        std::uniform_int_distribution<int> dist(a, b - 1);
        return dist(mt);
    }

    int operator()(int b) {
        return (*this)(0, b);
    }

    template <typename T>
    void shuffle(std::vector<T> &v) {
        std::shuffle(v.begin(), v.end(), mt);
    }
};

std::vector<long long> treeHash(std::vector<std::vector<int>> &edges, int root = 0,
                                const long long MOD = 998244353, int seed = 0) {
    int n = edges.size();
    std::vector<int> dist(n, -1);
    std::vector<int> route;
    std::stack<int> st;
    st.push(root);
    route.push_back(root);
    dist[root] = 0;
    while (!st.empty()) {
        int pos = st.top();
        st.pop();
        for (auto npos : edges[pos]) {
            if (dist[npos] == -1) {
                dist[npos] = dist[pos] + 1;
                st.push(npos);
                route.push_back(npos);
            }
        }
    }
    std::reverse(route.begin(), route.end());
    int d = 0;
    for (auto di : dist) d = std::max(d, di);
    std::vector<long long> X(d + 1);
    RandomNumberGenerator rng(seed);
    for (int i = 0; i <= d; i++) X[i] = rng(MOD);
    std::vector<int> ma(n, 0);
    std::vector<long long> hash(n, 1);
    for (auto pos : route) {
        for (auto npos : edges[pos]) {
            if (dist[npos] < dist[pos]) continue;
            ma[pos] = std::max(ma[pos], ma[npos] + 1);
        }
        auto x = X[ma[pos]];
        for (auto npos : edges[pos]) {
            if (dist[npos] < dist[pos]) continue;
            hash[pos] *= (x + hash[npos]);
            hash[pos] %= MOD;
        }
    }
    return hash;
}

std::vector<int> treeIsomorphism(std::vector<std::vector<int>> &edges1,
                                 std::vector<std::vector<int>> &edges2) {

    auto get_centroids = [&](std::vector<std::vector<int>> &edges) {
        int n = edges.size();
        std::vector<int> centroids;
        std::vector<int> sz(n);
        std::function<void(int, int)> dfs = [&](int pos, int par) {
            sz[pos]          = 1;
            bool is_centroid = true;
            for (auto npos : edges[pos]) {
                if (npos == par) continue;
                dfs(npos, pos);
                sz[pos] += sz[npos];
                if (sz[npos] > n / 2) is_centroid = false;
            }
            if (n - sz[pos] > n / 2) is_centroid = false;
            if (is_centroid) centroids.push_back(pos);
        };
        dfs(0, -1);
        return centroids;
    };

    auto cent1 = get_centroids(edges1);
    auto cent2 = get_centroids(edges2);

    RandomNumberGenerator rng;
    int seed1 = rng(1 << 30);
    int seed2 = rng(1 << 30);

    auto get_hash = [&](std::vector<std::vector<int>> &edges, int centroid) {
        const int MOD9 = 998244353;
        const int MOD1 = 1000000007;
        auto h1        = treeHash(edges, centroid, MOD9, seed1);
        auto h2        = treeHash(edges, centroid, MOD1, seed2);
        std::vector<long long> hash(h1.size());
        for (size_t i = 0; i < h1.size(); i++) {
            hash[i] = ((long long)(h1[i]) << 32) | h2[i];
        }
        return hash;
    };

    for (auto c1 : cent1) {
        auto h1 = get_hash(edges1, c1);
        for (auto c2 : cent2) {
            auto h2 = get_hash(edges2, c2);
            if (h1[c1] == h2[c2]) {
                std::vector<int> P(edges1.size(), -1);

                std::function<void(int, int, int, int)> dfs = [&](int pos1, int bpos1, int pos2,
                                                                  int bpos2) {
                    P[pos1] = pos2;
                    std::map<long long, std::vector<int>> mp;
                    for (auto npos2 : edges2[pos2]) {
                        if (npos2 == bpos2) continue;
                        mp[h2[npos2]].push_back(npos2);
                    }

                    for (auto npos1 : edges1[pos1]) {
                        if (npos1 == bpos1) continue;
                        int npos2 = mp[h1[npos1]].back();
                        mp[h1[npos1]].pop_back();
                        dfs(npos1, pos1, npos2, pos2);
                    }
                };

                dfs(c1, -1, c2, -1);
                return P;
            }
        }
    }
    return {};
}

void solve() {
    int n;
    cin >> n;
    int nex = n;
    vector<vector<int>> edges(n);
    for (int i = 0; i < n - 1; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        u--;
        v--;
        for (int j = 0; j < w - 1; j++) {
            edges.push_back({});
            edges[u].push_back(nex);
            edges[nex].push_back(u);
            u = nex;
            nex++;
        }
        edges[u].push_back(v);
        edges[v].push_back(u);
    }

    int h, w;
    cin >> h >> w;
    vector<vector<char>> S(h, vector<char>(w));
    for (auto &row : S) {
        for (auto &c : row) {
            cin >> c;
        }
    }
    vector<vector<int>> idx(h, vector<int>(w, -1));
    int n2 = 0;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            if (S[i][j] == '#') {
                idx[i][j] = n2++;
            }
        }
    }

    if (n2 != edges.size()) {
        cout << "No" << endl;
        return;
    }

    vector<vector<int>> edges2(n2);
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            if (S[i][j] != '#') continue;
            if (i > 0 and S[i - 1][j] == '#') {
                edges2[idx[i][j]].push_back(idx[i - 1][j]);
                edges2[idx[i - 1][j]].push_back(idx[i][j]);
            }
            if (j > 0 and S[i][j - 1] == '#') {
                edges2[idx[i][j]].push_back(idx[i][j - 1]);
                edges2[idx[i][j - 1]].push_back(idx[i][j]);
            }
        }
    }

    auto P = treeIsomorphism(edges, edges2);

    if (P.empty()) {
        cout << "No" << endl;
        return;
    }

    cout << "Yes" << endl;

    vector<pair<int, int>> to(n2);

    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            if (idx[i][j] != -1) {
                to[idx[i][j]] = {i + 1, j + 1};
            }
        }
    }

    for (int i = 0; i < n; i++) {
        int p = P[i];
        cout << to[p].first << " " << to[p].second << endl;
    }
}

int main() {
    int t;
    std::cin >> t;
    while (t--) solve();
    return 0;
}

// #include <bits/stdc++.h>
// using namespace std;
//
// #include "tree/treeIsomorphism.hpp"
//
// void solve() {
//     int n;
//     cin >> n;
//     int nex = n;
//     vector<vector<int>> edges(n);
//     for (int i = 0; i < n - 1; i++) {
//         int u, v, w;
//         cin >> u >> v >> w;
//         u--;
//         v--;
//         for (int j = 0; j < w - 1; j++) {
//             edges.push_back({});
//             edges[u].push_back(nex);
//             edges[nex].push_back(u);
//             u = nex;
//             nex++;
//         }
//         edges[u].push_back(v);
//         edges[v].push_back(u);
//     }
//
//     int h, w;
//     cin >> h >> w;
//     vector<vector<char>> S(h, vector<char>(w));
//     for (auto &row : S) {
//         for (auto &c : row) {
//             cin >> c;
//         }
//     }
//     vector<vector<int>> idx(h, vector<int>(w, -1));
//     int n2 = 0;
//     for (int i = 0; i < h; i++) {
//         for (int j = 0; j < w; j++) {
//             if (S[i][j] == '#') {
//                 idx[i][j] = n2++;
//             }
//         }
//     }
//
//     if (n2 != edges.size()) {
//         cout << "No" << endl;
//         return;
//     }
//
//     vector<vector<int>> edges2(n2);
//     for (int i = 0; i < h; i++) {
//         for (int j = 0; j < w; j++) {
//             if (S[i][j] != '#') continue;
//             if (i > 0 and S[i - 1][j] == '#') {
//                 edges2[idx[i][j]].push_back(idx[i - 1][j]);
//                 edges2[idx[i - 1][j]].push_back(idx[i][j]);
//             }
//             if (j > 0 and S[i][j - 1] == '#') {
//                 edges2[idx[i][j]].push_back(idx[i][j - 1]);
//                 edges2[idx[i][j - 1]].push_back(idx[i][j]);
//             }
//         }
//     }
//
//     auto P = treeIsomorphism(edges, edges2);
//
//     if (P.empty()) {
//         cout << "No" << endl;
//         return;
//     }
//
//     cout << "Yes" << endl;
//
//     vector<pair<int, int>> to(n2);
//
//     for (int i = 0; i < h; i++) {
//         for (int j = 0; j < w; j++) {
//             if (idx[i][j] != -1) {
//                 to[idx[i][j]] = {i + 1, j + 1};
//             }
//         }
//     }
//
//     for (int i = 0; i < n; i++) {
//         int p = P[i];
//         cout << to[p].first << " " << to[p].second << endl;
//     }
// }
//
// int main() {
//     int t;
//     std::cin >> t;
//     while (t--) solve();
//     return 0;
// }
0