結果

問題 No.2981 Pack Tree into Grid
コンテスト
ユーザー KumaTachiRen
提出日時 2024-11-29 21:36:57
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 20 ms / 2,000 ms
コード長 6,096 bytes
コンパイル時間 4,476 ms
コンパイル使用メモリ 284,912 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-12-04 23:31:41
合計ジャッジ時間 6,974 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

struct Fast
{
    Fast()
    {
        std::cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << setprecision(10);
    }
} fast;

#define all(a) (a).begin(), (a).end()
#define contains(a, x) ((a).find(x) != (a).end())
#define rep(i, a, b) for (int i = (a); i < (int)(b); i++)

using ll = long long;

struct RandomNumberGenerator
{
    mt19937 mt;
    RandomNumberGenerator() : mt(chrono::steady_clock::now().time_since_epoch().count()) {}
    int operator()(int n)
    {
        uniform_int_distribution<int> dist(0, n - 1);
        return dist(mt);
    }
};

void calc_distance(const vector<vector<int>> &g, const int root, vector<int> &dist, vector<int> &prev, int &last_vertex)
{
    queue<int> qu;
    qu.push(root);
    dist[root] = 0;
    prev[root] = -1;
    while (!qu.empty())
    {
        auto x = qu.front();
        qu.pop();
        last_vertex = x;
        for (auto y : g[x])
            if (prev[x] != y)
            {
                qu.push(y);
                dist[y] = dist[x] + 1;
                prev[y] = x;
            }
    }
}

pair<int, int> find_center(const vector<vector<int>> &g)
{
    int u, v;
    vector<int> dist(g.size(), 0), prev(g.size(), -1);
    calc_distance(g, 0, dist, prev, u);
    calc_distance(g, u, dist, prev, v);
    int d = dist[v] / 2, x = v;
    rep(i, 0, d) x = prev[x];
    return {x, (dist[v] & 1) ? prev[x] : -1};
}

bool solve_rooted(const int N, const vector<vector<int>> &T1, const vector<vector<int>> &T2, const vector<pair<int, int>> &T2_pos, const int T1_root, const int T2_root)
{
    if (T1_root == -1 || T2_root == -1) return false;

    RandomNumberGenerator rnd;

    using mint = atcoder::modint998244353;

    vector<vector<mint>> T1_hash, T2_hash;
    rep(k, 0, 2)
    {
        vector<int> depth_val;

        auto dfs = [&](auto self, int x, int p, const vector<vector<int>> &T, vector<mint> &hash) -> int
        {
            int d = 0;
            mint prod = 1;
            for (auto y : T[x])
            {
                if (y == p) continue;
                d = max(d, self(self, y, x, T, hash) + 1);
                prod *= hash[y];
            }
            while (depth_val.size() <= d)
                depth_val.push_back(rnd(mint::mod()));
            hash[x] = depth_val[d] + prod;
            return d;
        };

        vector<mint> T1_hash_tmp(T1.size()), T2_hash_tmp(T2.size());
        dfs(dfs, T1_root, -1, T1, T1_hash_tmp);
        dfs(dfs, T2_root, -1, T2, T2_hash_tmp);
        if (T1_hash_tmp[T1_root] != T2_hash_tmp[T2_root]) return false;
        T1_hash.push_back(T1_hash_tmp);
        T2_hash.push_back(T2_hash_tmp);
    }

    vector<pair<int, int>> ans(N, {-1, -1});
    auto dfs2 = [&](auto self, int x1, int p1, int x2, int p2) -> void
    {
        if (x1 < N) ans[x1] = T2_pos[x2];
        vector<pair<int, int>> children1, children2;
        for (auto y : T1[x1])
            if (y != p1) children1.push_back({(uint64_t(T1_hash[0][y].val()) << 32) + T1_hash[1][y].val(), y});
        for (auto y : T2[x2])
            if (y != p2) children2.push_back({(uint64_t(T2_hash[0][y].val()) << 32) + T2_hash[1][y].val(), y});
        sort(all(children1));
        sort(all(children2));
        rep(i, 0, children1.size()) self(self, children1[i].second, x1, children2[i].second, x2);
    };
    dfs2(dfs2, T1_root, -1, T2_root, -1);
    cout << "Yes" << "\n";
    rep(i, 0, N)
    {
        auto [x, y] = ans[i];
        cout << (x + 1) << " " << (y + 1) << "\n";
    }
    return true;
}

void solve()
{
    int N, H, W;
    cin >> N;
    vector<tuple<int, int, int>> T;
    rep(i, 0, N - 1)
    {
        int u, v, w;
        cin >> u >> v >> w;
        T.push_back({u, v, w});
    }
    cin >> H >> W;
    vector<string> S(H);
    rep(i, 0, H) cin >> S[i];

    size_t T1_size = 1, T2_size = 0;
    for (auto [u, v, w] : T)
        T1_size += w;
    rep(i, 0, H) rep(j, 0, W) T2_size += S[i][j] == '#';

    if (T1_size != T2_size)
    {
        cout << "No" << "\n";
        return;
    }

    vector<vector<int>> T1(T1_size, vector<int>()), T2(T2_size, vector<int>());
    vector<pair<int, int>> T2_pos;
    {
        size_t dummy = N;
        for (auto [u, v, w] : T)
        {
            u--, v--;
            if (w == 1)
            {
                T1[u].push_back(v), T1[v].push_back(u);
            }
            else
            {
                T1[u].push_back(dummy), T1[dummy].push_back(u);
                rep(i, 0, w - 2)
                {
                    T1[dummy].push_back(dummy + 1), T1[dummy + 1].push_back(dummy);
                    dummy++;
                }
                T1[v].push_back(dummy), T1[dummy].push_back(v);
                dummy++;
            }
        }
    }
    {
        vector<vector<int>> T2_index(H, vector<int>(W, -1));
        rep(i, 0, H) rep(j, 0, W) if (S[i][j] == '#') T2_index[i][j] = T2_pos.size(), T2_pos.push_back({i, j});
        rep(i, 0, T2.size())
        {
            auto [x1, y1] = T2_pos[i];
            rep(k, 0, 4)
            {
                int x2 = x1 + (k & 1 ? 0 : 1 - k);
                int y2 = y1 + (k & 1 ? 2 - k : 0);
                if (x2 < 0 || x2 >= H || y2 < 0 || y2 >= W) continue;
                if (T2_index[x2][y2] != -1) T2[i].push_back(T2_index[x2][y2]);
            }
        }
    }

    size_t T1_deg_max = 0, T2_deg_max = 0;
    rep(i, 0, T1_size) T1_deg_max = max(T1_deg_max, T1[i].size());
    rep(i, 0, T2_size) T2_deg_max = max(T2_deg_max, T2[i].size());
    if (T1_deg_max != T2_deg_max)
    {
        cout << "No" << "\n";
        return;
    }

    auto [T1_c1, T1_c2] = find_center(T1);
    auto [T2_c1, T2_c2] = find_center(T2);

    if (solve_rooted(N, T1, T2, T2_pos, T1_c1, T2_c1)) return;
    if (solve_rooted(N, T1, T2, T2_pos, T1_c1, T2_c2)) return;
    if (solve_rooted(N, T1, T2, T2_pos, T1_c2, T2_c1)) return;
    if (solve_rooted(N, T1, T2, T2_pos, T1_c2, T2_c2)) return;

    cout << "No" << "\n";
}

int main()
{
    int t = 1;
    cin >> t;
    while (t--)
        solve();
}
0