結果

問題 No.2981 Pack Tree into Grid
ユーザー KumaTachiRen
提出日時 2024-11-20 00:46:50
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 12 ms / 2,000 ms
コード長 5,637 bytes
コンパイル時間 3,820 ms
コンパイル使用メモリ 286,976 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-12-04 23:30:08
合計ジャッジ時間 6,216 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
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;
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;
    const ll class_coeff = 1000;
    map<ll, int> class_map;
    class_map[0] = 1;
    auto dfs = [&](auto self, int x, int p, const vector<vector<int>> &T, vector<int> &class_ids) -> void
    {
        vector<int> children_ids;
        for (auto y : T[x])
        {
            if (y == p) continue;
            self(self, y, x, T, class_ids);
            children_ids.push_back(class_ids[y]);
        }
        sort(all(children_ids));
        ll children_id = 0;
        for (auto v : children_ids)
            children_id = children_id * class_coeff + v;
        if (!contains(class_map, children_id)) class_map[children_id] = class_map.size() + 1;
        class_ids[x] = class_map[children_id];
    };
    vector<int> T1_class_ids(T1.size(), -1), T2_class_ids(T2.size(), -1);
    dfs(dfs, T1_root, -1, T1, T1_class_ids);
    dfs(dfs, T2_root, -1, T2, T2_class_ids);
    if (T1_class_ids[T1_root] != T2_class_ids[T2_root]) return false;
    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({T1_class_ids[y], y});
        for (auto y : T2[x2])
            if (y != p2) children2.push_back({T2_class_ids[y], 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();
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0