結果

問題 No.2981 Pack Tree into Grid
ユーザー 👑 hos.lyric
提出日時 2024-12-06 00:23:27
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 76 ms / 2,000 ms
コード長 4,289 bytes
コンパイル時間 1,430 ms
コンパイル使用メモリ 129,948 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-12-06 00:23:32
合計ジャッジ時間 3,946 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

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

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
using Int = long long;
template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i 
    >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")
int I;
map<vector<int>, int> tr;
void init() {
  I = 0;
  tr.clear();
}
int id(const vector<int> &seq) {
  auto it = tr.find(seq);
  if (it != tr.end()) return it->second;
  return tr[seq] = I++;
}
struct Tree {
  int n;
  vector<vector<int>> graph;
  void init(int n_) {
    n = n_;
    graph.assign(n, {});
  }
  void ae(int u, int v) {
    graph[u].push_back(v);
    graph[v].push_back(u);
  }
  vector<int> dp;
  void dfs(int u, int p) {
    vector<int> seq;
    for (const int v : graph[u]) if (p != v) {
      dfs(v, u);
      seq.push_back(dp[v]);
    }
    sort(seq.begin(), seq.end());
    dp[u] = id(seq);
  }
  void run(int r) {
    dp.assign(n, -1);
    dfs(r, -1);
  }
} T[2];
int N;
vector<int> A, B, C;
int H, W;
char S[30][30];
bool inside(int x, int y) {
  return (0 <= x && x < H && 0 <= y && y < W && S[x][y] == '#');
}
int K;
int ids[30][30];
vector<int> X, Y;
vector<int> ans;
void recover(int u0, int p0, int u1, int p1) {
  ans[u0] = u1;
  vector<int> vs0, vs1;
  for (const int v : T[0].graph[u0]) if (v != p0) vs0.push_back(v);
  for (const int v : T[1].graph[u1]) if (v != p1) vs1.push_back(v);
  assert(vs0.size() == vs1.size());
  for (const int v0 : vs0) {
    for (int i = 0; i < (int)vs1.size(); ++i) {
      const int v1 = vs1[i];
      if (T[0].dp[v0] == T[1].dp[v1]) {
        recover(v0, u0, v1, u1);
        vs1.erase(vs1.begin() + i);
        break;
      }
    }
  }
  assert(!vs1.size());
}
bool solve() {
  init();
  
  K = 0;
  memset(ids, ~0, sizeof(ids));
  X.clear();
  Y.clear();
  for (int x = 0; x < H; ++x) for (int y = 0; y < W; ++y) if (inside(x, y)) {
    ids[x][y] = K++;
    X.push_back(x);
    Y.push_back(y);
  }
  T[1].init(K);
  for (int x = 0; x < H; ++x) for (int y = 0; y < W; ++y) if (inside(x, y)) {
    if (inside(x + 1, y)) T[1].ae(ids[x][y], ids[x + 1][y]);
    if (inside(x, y + 1)) T[1].ae(ids[x][y], ids[x][y + 1]);
  }
  
  int n = N;
  for (int i = 0; i < N - 1; ++i) n += (C[i] - 1);
  if (n != K) return false;
  T[0].init(n);
  n = N;
  for (int i = 0; i < N - 1; ++i) {
    int u = A[i];
    for (int c = 1; c < C[i]; ++c) {
      const int v = n++;
      T[0].ae(u, v);
      u = v;
    }
    T[0].ae(u, B[i]);
  }
  
  T[0].run(0);
  for (int r = 0; r < K; ++r) {
    T[1].run(r);
    if (T[0].dp[0] == T[1].dp[r]) {
      ans.resize(K, -1);
      recover(0, -1, r, -1);
      puts("Yes");
      for (int u = 0; u < N; ++u) {
        printf("%d %d\n", X[ans[u]] + 1, Y[ans[u]] + 1);
      }
      return true;
    }
  }
  
  return false;
}
int main() {
  for (int numCases; ~scanf("%d", &numCases); ) { for (int caseId = 1; caseId <= numCases; ++caseId) {
    scanf("%d", &N);
    A.resize(N - 1);
    B.resize(N - 1);
    C.resize(N - 1);
    for (int i = 0; i < N - 1; ++i) {
      scanf("%d%d%d", &A[i], &B[i], &C[i]);
      --A[i];
      --B[i];
    }
    scanf("%d%d", &H, &W);
    for (int x = 0; x < H; ++x) {
      scanf("%s", S[x]);
    }
    
    const bool res = solve();
    if (!res) {
      puts("No");
    }
  }
#ifndef LOCAL
  break;
#endif
  }
  return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0