結果
問題 | No.2981 Pack Tree into Grid |
ユーザー |
![]() |
提出日時 | 2024-12-05 00:27:37 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 394 ms / 2,000 ms |
コード長 | 43,619 bytes |
コンパイル時間 | 4,638 ms |
コンパイル使用メモリ | 269,376 KB |
実行使用メモリ | 14,104 KB |
最終ジャッジ日時 | 2024-12-05 00:27:47 |
合計ジャッジ時間 | 8,901 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 28 |
ソースコード
#include <algorithm> #include <array> #include <bitset> #include <cassert> #include <chrono> #include <cmath> #include <complex> #include <deque> #include <forward_list> #include <fstream> #include <functional> #include <iomanip> #include <ios> #include <iostream> #include <limits> #include <list> #include <map> #include <memory> #include <numeric> #include <optional> #include <queue> #include <random> #include <set> #include <sstream> #include <stack> #include <string> #include <tuple> #include <type_traits> #include <unordered_map> #include <unordered_set> #include <utility> #include <vector> using namespace std; using lint = long long; using pint = pair<int, int>; using plint = pair<lint, lint>; struct fast_ios { fast_ios(){ cin.tie(nullptr), ios::sync_with_stdio(false), cout << fixed << setprecision(20); }; } fast_ios_; #define ALL(x) (x).begin(), (x).end() #define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++) #define IFOR(i, begin, end) for(int i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--) #define REP(i, n) FOR(i,0,n) #define IREP(i, n) IFOR(i,0,n) template <typename T> bool chmax(T &m, const T q) { return m < q ? (m = q, true) : false; } template <typename T> bool chmin(T &m, const T q) { return m > q ? (m = q, true) : false; } const std::vector<std::pair<int, int>> grid_dxs{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; int floor_lg(long long x) { return x <= 0 ? -1 : 63 - __builtin_clzll(x); } template <class T1, class T2> T1 floor_div(T1 num, T2 den) { return (num > 0 ? num / den : -((-num + den - 1) / den)); } template <class T1, class T2> std::pair<T1, T2> operator+(const std::pair<T1, T2> &l, const std::pair<T1, T2> &r) { return std::make_pair(l.first + r.first, l.second + r.second); } template <class T1, class T2> std::pair<T1, T2> operator-(const std::pair<T1, T2> &l, const std::pair<T1, T2> &r) { return std::make_pair(l.first - r.first, l.second - r.second); } template <class T> std::vector<T> sort_unique(std::vector<T> vec) { sort(vec.begin(), vec.end()), vec.erase(unique(vec.begin(), vec.end()), vec.end()); return vec; } template <class T> int arglb(const std::vector<T> &v, const T &x) { return std::distance(v.begin(), std::lower_bound(v.begin(), v.end(), x)); } template <class T> int argub(const std::vector<T> &v, const T &x) { return std::distance(v.begin(), std::upper_bound(v.begin(), v.end(), x)); } template <class IStream, class T> IStream &operator>>(IStream &is, std::vector<T> &vec) { for (auto &v : vec) is >> v; return is; } template <class OStream, class T> OStream &operator<<(OStream &os, const std::vector<T> &vec); template <class OStream, class T, size_t sz> OStream &operator<<(OStream &os, const std::array<T, sz> &arr); template <class OStream, class T, class TH> OStream &operator<<(OStream &os, const std::unordered_set<T, TH> &vec); template <class OStream, class T, class U> OStream &operator<<(OStream &os, const pair<T, U> &pa); template <class OStream, class T> OStream &operator<<(OStream &os, const std::deque<T> &vec); template <class OStream, class T> OStream &operator<<(OStream &os, const std::set<T> &vec); template <class OStream, class T> OStream &operator<<(OStream &os, const std::multiset<T> &vec); template <class OStream, class T> OStream &operator<<(OStream &os, const std::unordered_multiset<T> &vec); template <class OStream, class T, class U> OStream &operator<<(OStream &os, const std::pair<T, U> &pa); template <class OStream, class TK, class TV> OStream &operator<<(OStream &os, const std::map<TK, TV> &mp); template <class OStream, class TK, class TV, class TH> OStream &operator<<(OStream &os, const std::unordered_map<TK, TV, TH> &mp); template <class OStream, class... T> OStream &operator<<(OStream &os, const std::tuple<T...> &tpl); template <class OStream, class T> OStream &operator<<(OStream &os, const std::vector<T> &vec) { os << '['; for (auto v : vec) os << v << ','; os << ']'; return os; } template <class OStream, class T, size_t sz> OStream &operator<<(OStream &os, const std::array<T, sz> &arr) { os << '['; for (auto v : arr) os << v << ','; os << ']'; return os; } template <class... T> std::istream &operator>>(std::istream &is, std::tuple<T...> &tpl) { std::apply([&is](auto &&... args) { ((is >> args), ...);}, tpl); return is; } template <class OStream, class... T> OStream &operator<<(OStream &os, const std::tuple<T...> &tpl) { os << '('; std::apply([&os](auto &&... args) { ((os << args << ','), ...);}, tpl); return os << ')'; } template <class OStream, class T, class TH> OStream &operator<<(OStream &os, const std::unordered_set<T, TH> &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}'; return os; } template <class OStream, class T> OStream &operator<<(OStream &os, const std::deque<T> &vec) { os << "deq["; for (auto v : vec) os << v << ','; os << ']'; return os; } template <class OStream, class T> OStream &operator<<(OStream &os, const std::set<T> &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}'; return os; } template <class OStream, class T> OStream &operator<<(OStream &os, const std::multiset<T> &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}'; return os; } template <class OStream, class T> OStream &operator<<(OStream &os, const std::unordered_multiset<T> &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}'; return os; } template <class OStream, class T, class U> OStream &operator<<(OStream &os, const std::pair<T, U> &pa) { return os << '(' << pa.first << ',' << pa.second << ')'; } template <class OStream, class TK, class TV> OStream &operator<<(OStream &os, const std::map<TK, TV> &mp) { os << '{'; for (auto v : mp) os << v.first << "=>" << v.second << ','; os << '}'; return os; } template <class OStream, class TK, class TV, class TH> OStream &operator<<(OStream &os, const std::unordered_map<TK, TV, TH> &mp) { os << '{'; for (auto v : mp) os << v.first << "=>" << v.second << ','; os << '}'; return os; } #ifdef HITONANODE_LOCAL const string COLOR_RESET = "\033[0m", BRIGHT_GREEN = "\033[1;32m", BRIGHT_RED = "\033[1;31m", BRIGHT_CYAN = "\033[1;36m", NORMAL_CROSSED = "\033[0;9;37m", RED_BACKGROUND = "\033[1;41m", NORMAL_FAINT = "\033[0;2m"; #define dbg(x) std::cerr << BRIGHT_CYAN << #x << COLOR_RESET << " = " << (x) << NORMAL_FAINT << " (L" << __LINE__ << ") " << __FILE__ << COLOR_RESET << std::endl #define dbgif(cond, x) ((cond) ? std::cerr << BRIGHT_CYAN << #x << COLOR_RESET << " = " << (x) << NORMAL_FAINT << " (L" << __LINE__ << ") " << __FILE__ << COLOR_RESET << std::endl : std::cerr) #else #define dbg(x) ((void)0) #define dbgif(cond, x) ((void)0) #endif #include <algorithm> #include <cassert> #include <deque> #include <fstream> #include <functional> #include <limits> #include <queue> #include <string> #include <tuple> #include <utility> #include <vector> template <typename T, T INF = std::numeric_limits<T>::max() / 2, int INVALID = -1> struct shortest_path { int V, E; bool single_positive_weight; T wmin, wmax; std::vector<std::pair<int, T>> tos; std::vector<int> head; std::vector<std::tuple<int, int, T>> edges; void build_() { if (int(tos.size()) == E and int(head.size()) == V + 1) return; tos.resize(E); head.assign(V + 1, 0); for (const auto &e : edges) ++head[std::get<0>(e) + 1]; for (int i = 0; i < V; ++i) head[i + 1] += head[i]; auto cur = head; for (const auto &e : edges) { tos[cur[std::get<0>(e)]++] = std::make_pair(std::get<1>(e), std::get<2>(e)); } } shortest_path(int V = 0) : V(V), E(0), single_positive_weight(true), wmin(0), wmax(0) {} void add_edge(int s, int t, T w) { assert(0 <= s and s < V); assert(0 <= t and t < V); edges.emplace_back(s, t, w); ++E; if (w > 0 and wmax > 0 and wmax != w) single_positive_weight = false; wmin = std::min(wmin, w); wmax = std::max(wmax, w); } void add_bi_edge(int u, int v, T w) { add_edge(u, v, w); add_edge(v, u, w); } std::vector<T> dist; std::vector<int> prev; // Dijkstra algorithm // - Requirement: wmin >= 0 // - Complexity: O(E log E) using Pque = std::priority_queue<std::pair<T, int>, std::vector<std::pair<T, int>>, std::greater<std::pair<T, int>>>; template <class Heap = Pque> void dijkstra(int s, int t = INVALID) { assert(0 <= s and s < V); build_(); dist.assign(V, INF); prev.assign(V, INVALID); dist[s] = 0; Heap pq; pq.emplace(0, s); while (!pq.empty()) { T d; int v; std::tie(d, v) = pq.top(); pq.pop(); if (t == v) return; if (dist[v] < d) continue; for (int e = head[v]; e < head[v + 1]; ++e) { const auto &nx = tos[e]; T dnx = d + nx.second; if (dist[nx.first] > dnx) { dist[nx.first] = dnx, prev[nx.first] = v; pq.emplace(dnx, nx.first); } } } } // Dijkstra algorithm // - Requirement: wmin >= 0 // - Complexity: O(V^2 + E) void dijkstra_vquad(int s, int t = INVALID) { assert(0 <= s and s < V); build_(); dist.assign(V, INF); prev.assign(V, INVALID); dist[s] = 0; std::vector<char> fixed(V, false); while (true) { int r = INVALID; T dr = INF; for (int i = 0; i < V; i++) { if (!fixed[i] and dist[i] < dr) r = i, dr = dist[i]; } if (r == INVALID or r == t) break; fixed[r] = true; int nxt; T dx; for (int e = head[r]; e < head[r + 1]; ++e) { std::tie(nxt, dx) = tos[e]; if (dist[nxt] > dist[r] + dx) dist[nxt] = dist[r] + dx, prev[nxt] = r; } } } // Bellman-Ford algorithm // - Requirement: no negative loop // - Complexity: O(VE) bool bellman_ford(int s, int nb_loop) { assert(0 <= s and s < V); build_(); dist.assign(V, INF), prev.assign(V, INVALID); dist[s] = 0; for (int l = 0; l < nb_loop; l++) { bool upd = false; for (int v = 0; v < V; v++) { if (dist[v] == INF) continue; for (int e = head[v]; e < head[v + 1]; ++e) { const auto &nx = tos[e]; T dnx = dist[v] + nx.second; if (dist[nx.first] > dnx) dist[nx.first] = dnx, prev[nx.first] = v, upd = true; } } if (!upd) return true; } return false; } // Bellman-ford algorithm using deque // - Requirement: no negative loop // - Complexity: O(VE) void spfa(int s) { assert(0 <= s and s < V); build_(); dist.assign(V, INF); prev.assign(V, INVALID); dist[s] = 0; std::deque<int> q; std::vector<char> in_queue(V); q.push_back(s), in_queue[s] = 1; while (!q.empty()) { int now = q.front(); q.pop_front(), in_queue[now] = 0; for (int e = head[now]; e < head[now + 1]; ++e) { const auto &nx = tos[e]; T dnx = dist[now] + nx.second; int nxt = nx.first; if (dist[nxt] > dnx) { dist[nxt] = dnx; if (!in_queue[nxt]) { if (q.size() and dnx < dist[q.front()]) { // Small label first optimization q.push_front(nxt); } else { q.push_back(nxt); } prev[nxt] = now, in_queue[nxt] = 1; } } } } } // 01-BFS // - Requirement: all weights must be 0 or w (positive constant). // - Complexity: O(V + E) void zero_one_bfs(int s, int t = INVALID) { assert(0 <= s and s < V); build_(); dist.assign(V, INF), prev.assign(V, INVALID); dist[s] = 0; std::vector<int> q(V * 4); int ql = V * 2, qr = V * 2; q[qr++] = s; while (ql < qr) { int v = q[ql++]; if (v == t) return; for (int e = head[v]; e < head[v + 1]; ++e) { const auto &nx = tos[e]; T dnx = dist[v] + nx.second; if (dist[nx.first] > dnx) { dist[nx.first] = dnx, prev[nx.first] = v; if (nx.second) { q[qr++] = nx.first; } else { q[--ql] = nx.first; } } } } } // Dial's algorithm // - Requirement: wmin >= 0 // - Complexity: O(wmax * V + E) void dial(int s, int t = INVALID) { assert(0 <= s and s < V); build_(); dist.assign(V, INF), prev.assign(V, INVALID); dist[s] = 0; std::vector<std::vector<std::pair<int, T>>> q(wmax + 1); q[0].emplace_back(s, dist[s]); int ninq = 1; int cur = 0; T dcur = 0; for (; ninq; ++cur, ++dcur) { if (cur == wmax + 1) cur = 0; while (!q[cur].empty()) { int v = q[cur].back().first; T dnow = q[cur].back().second; q[cur].pop_back(), --ninq; if (v == t) return; if (dist[v] < dnow) continue; for (int e = head[v]; e < head[v + 1]; ++e) { const auto &nx = tos[e]; T dnx = dist[v] + nx.second; if (dist[nx.first] > dnx) { dist[nx.first] = dnx, prev[nx.first] = v; int nxtcur = cur + int(nx.second); if (nxtcur >= int(q.size())) nxtcur -= q.size(); q[nxtcur].emplace_back(nx.first, dnx), ++ninq; } } } } } // Solver for DAG // - Requirement: graph is DAG // - Complexity: O(V + E) bool dag_solver(int s) { assert(0 <= s and s < V); build_(); dist.assign(V, INF), prev.assign(V, INVALID); dist[s] = 0; std::vector<int> indeg(V, 0); std::vector<int> q(V * 2); int ql = 0, qr = 0; q[qr++] = s; while (ql < qr) { int now = q[ql++]; for (int e = head[now]; e < head[now + 1]; ++e) { const auto &nx = tos[e]; ++indeg[nx.first]; if (indeg[nx.first] == 1) q[qr++] = nx.first; } } ql = qr = 0; q[qr++] = s; while (ql < qr) { int now = q[ql++]; for (int e = head[now]; e < head[now + 1]; ++e) { const auto &nx = tos[e]; --indeg[nx.first]; if (dist[nx.first] > dist[now] + nx.second) dist[nx.first] = dist[now] + nx.second, prev[nx.first] = now; if (indeg[nx.first] == 0) q[qr++] = nx.first; } } return *max_element(indeg.begin(), indeg.end()) == 0; } // Retrieve a sequence of vertex ids that represents shortest path [s, ..., goal] // If not reachable to goal, return {} std::vector<int> retrieve_path(int goal) const { assert(int(prev.size()) == V); assert(0 <= goal and goal < V); if (dist[goal] == INF) return {}; std::vector<int> ret{goal}; while (prev[goal] != INVALID) { goal = prev[goal]; ret.push_back(goal); } std::reverse(ret.begin(), ret.end()); return ret; } void solve(int s, int t = INVALID) { if (wmin >= 0) { if (single_positive_weight) { zero_one_bfs(s, t); } else if (wmax <= 10) { dial(s, t); } else { if ((long long)V * V < (E << 4)) { dijkstra_vquad(s, t); } else { dijkstra(s, t); } } } else { bellman_ford(s, V); } } // Warshall-Floyd algorithm // - Requirement: no negative loop // - Complexity: O(E + V^3) std::vector<std::vector<T>> floyd_warshall() { build_(); std::vector<std::vector<T>> dist2d(V, std::vector<T>(V, INF)); for (int i = 0; i < V; i++) { dist2d[i][i] = 0; for (const auto &e : edges) { int s = std::get<0>(e), t = std::get<1>(e); dist2d[s][t] = std::min(dist2d[s][t], std::get<2>(e)); } } for (int k = 0; k < V; k++) { for (int i = 0; i < V; i++) { if (dist2d[i][k] == INF) continue; for (int j = 0; j < V; j++) { if (dist2d[k][j] == INF) continue; dist2d[i][j] = std::min(dist2d[i][j], dist2d[i][k] + dist2d[k][j]); } } } return dist2d; } void to_dot(std::string filename = "shortest_path") const { std::ofstream ss(filename + ".DOT"); ss << "digraph{\n"; build_(); for (int i = 0; i < V; i++) { for (int e = head[i]; e < head[i + 1]; ++e) { ss << i << "->" << tos[e].first << "[label=" << tos[e].second << "];\n"; } } ss << "}\n"; ss.close(); return; } }; #include <cassert> #include <chrono> #include <random> // F_p, p = 2^61 - 1 // https://qiita.com/keymoon/items/11fac5627672a6d6a9f6 class ModIntMersenne61 { static const long long md = (1LL << 61) - 1; long long _v; inline unsigned hi() const noexcept { return _v >> 31; } inline unsigned lo() const noexcept { return _v & ((1LL << 31) - 1); } public: static long long mod() { return md; } ModIntMersenne61() : _v(0) {} // 0 <= x < md * 2 explicit ModIntMersenne61(long long x) : _v(x >= md ? x - md : x) {} long long val() const noexcept { return _v; } ModIntMersenne61 operator+(const ModIntMersenne61 &x) const { return ModIntMersenne61(_v + x._v); } ModIntMersenne61 operator-(const ModIntMersenne61 &x) const { return ModIntMersenne61(_v + md - x._v); } ModIntMersenne61 operator*(const ModIntMersenne61 &x) const { using ull = unsigned long long; ull uu = (ull)hi() * x.hi() * 2; ull ll = (ull)lo() * x.lo(); ull lu = (ull)hi() * x.lo() + (ull)lo() * x.hi(); ull sum = uu + ll + ((lu & ((1ULL << 30) - 1)) << 31) + (lu >> 30); ull reduced = (sum >> 61) + (sum & ull(md)); return ModIntMersenne61(reduced); } ModIntMersenne61 pow(long long n) const { assert(n >= 0); ModIntMersenne61 ans(1), tmp = *this; while (n) { if (n & 1) ans *= tmp; tmp *= tmp, n >>= 1; } return ans; } ModIntMersenne61 inv() const { return pow(md - 2); } ModIntMersenne61 operator/(const ModIntMersenne61 &x) const { return *this * x.inv(); } ModIntMersenne61 operator-() const { return ModIntMersenne61(md - _v); } ModIntMersenne61 &operator+=(const ModIntMersenne61 &x) { return *this = *this + x; } ModIntMersenne61 &operator-=(const ModIntMersenne61 &x) { return *this = *this - x; } ModIntMersenne61 &operator*=(const ModIntMersenne61 &x) { return *this = *this * x; } ModIntMersenne61 &operator/=(const ModIntMersenne61 &x) { return *this = *this / x; } ModIntMersenne61 operator+(unsigned x) const { return ModIntMersenne61(this->_v + x); } bool operator==(const ModIntMersenne61 &x) const { return _v == x._v; } bool operator!=(const ModIntMersenne61 &x) const { return _v != x._v; } bool operator<(const ModIntMersenne61 &x) const { return _v < x._v; } // To use std::map template <class OStream> friend OStream &operator<<(OStream &os, const ModIntMersenne61 &x) { return os << x._v; } static ModIntMersenne61 randgen(bool force_update = false) { static ModIntMersenne61 b(0); if (b == ModIntMersenne61(0) or force_update) { std::mt19937 mt(std::chrono::steady_clock::now().time_since_epoch().count()); std::uniform_int_distribution<long long> d(1, ModIntMersenne61::mod()); b = ModIntMersenne61(d(mt)); } return b; } }; #include <cassert> #include <iostream> #include <set> #include <vector> template <int md> struct ModInt { using lint = long long; constexpr static int mod() { return md; } static int get_primitive_root() { static int primitive_root = 0; if (!primitive_root) { primitive_root = [&]() { std::set<int> fac; int v = md - 1; for (lint i = 2; i * i <= v; i++) while (v % i == 0) fac.insert(i), v /= i; if (v > 1) fac.insert(v); for (int g = 1; g < md; g++) { bool ok = true; for (auto i : fac) if (ModInt(g).pow((md - 1) / i) == 1) { ok = false; break; } if (ok) return g; } return -1; }(); } return primitive_root; } int val_; int val() const noexcept { return val_; } constexpr ModInt() : val_(0) {} constexpr ModInt &_setval(lint v) { return val_ = (v >= md ? v - md : v), *this; } constexpr ModInt(lint v) { _setval(v % md + md); } constexpr explicit operator bool() const { return val_ != 0; } constexpr ModInt operator+(const ModInt &x) const { return ModInt()._setval((lint)val_ + x.val_); } constexpr ModInt operator-(const ModInt &x) const { return ModInt()._setval((lint)val_ - x.val_ + md); } constexpr ModInt operator*(const ModInt &x) const { return ModInt()._setval((lint)val_ * x.val_ % md); } constexpr ModInt operator/(const ModInt &x) const { return ModInt()._setval((lint)val_ * x.inv().val() % md); } constexpr ModInt operator-() const { return ModInt()._setval(md - val_); } constexpr ModInt &operator+=(const ModInt &x) { return *this = *this + x; } constexpr ModInt &operator-=(const ModInt &x) { return *this = *this - x; } constexpr ModInt &operator*=(const ModInt &x) { return *this = *this * x; } constexpr ModInt &operator/=(const ModInt &x) { return *this = *this / x; } friend constexpr ModInt operator+(lint a, const ModInt &x) { return ModInt(a) + x; } friend constexpr ModInt operator-(lint a, const ModInt &x) { return ModInt(a) - x; } friend constexpr ModInt operator*(lint a, const ModInt &x) { return ModInt(a) * x; } friend constexpr ModInt operator/(lint a, const ModInt &x) { return ModInt(a) / x; } constexpr bool operator==(const ModInt &x) const { return val_ == x.val_; } constexpr bool operator!=(const ModInt &x) const { return val_ != x.val_; } constexpr bool operator<(const ModInt &x) const { return val_ < x.val_; } // To use std::map<ModInt, T> friend std::istream &operator>>(std::istream &is, ModInt &x) { lint t; return is >> t, x = ModInt(t), is; } constexpr friend std::ostream &operator<<(std::ostream &os, const ModInt &x) { return os << x.val_; } constexpr ModInt pow(lint n) const { ModInt ans = 1, tmp = *this; while (n) { if (n & 1) ans *= tmp; tmp *= tmp, n >>= 1; } return ans; } static constexpr int cache_limit = std::min(md, 1 << 21); static std::vector<ModInt> facs, facinvs, invs; constexpr static void _precalculation(int N) { const int l0 = facs.size(); if (N > md) N = md; if (N <= l0) return; facs.resize(N), facinvs.resize(N), invs.resize(N); for (int i = l0; i < N; i++) facs[i] = facs[i - 1] * i; facinvs[N - 1] = facs.back().pow(md - 2); for (int i = N - 2; i >= l0; i--) facinvs[i] = facinvs[i + 1] * (i + 1); for (int i = N - 1; i >= l0; i--) invs[i] = facinvs[i] * facs[i - 1]; } constexpr ModInt inv() const { if (this->val_ < cache_limit) { if (facs.empty()) facs = {1}, facinvs = {1}, invs = {0}; while (this->val_ >= int(facs.size())) _precalculation(facs.size() * 2); return invs[this->val_]; } else { return this->pow(md - 2); } } constexpr ModInt fac() const { while (this->val_ >= int(facs.size())) _precalculation(facs.size() * 2); return facs[this->val_]; } constexpr ModInt facinv() const { while (this->val_ >= int(facs.size())) _precalculation(facs.size() * 2); return facinvs[this->val_]; } constexpr ModInt doublefac() const { lint k = (this->val_ + 1) / 2; return (this->val_ & 1) ? ModInt(k * 2).fac() / (ModInt(2).pow(k) * ModInt(k).fac()) : ModInt(k).fac() * ModInt(2).pow(k); } constexpr ModInt nCr(int r) const { if (r < 0 or this->val_ < r) return ModInt(0); return this->fac() * (*this - r).facinv() * ModInt(r).facinv(); } constexpr ModInt nPr(int r) const { if (r < 0 or this->val_ < r) return ModInt(0); return this->fac() * (*this - r).facinv(); } static ModInt binom(int n, int r) { static long long bruteforce_times = 0; if (r < 0 or n < r) return ModInt(0); if (n <= bruteforce_times or n < (int)facs.size()) return ModInt(n).nCr(r); r = std::min(r, n - r); ModInt ret = ModInt(r).facinv(); for (int i = 0; i < r; ++i) ret *= n - i; bruteforce_times += r; return ret; } // Multinomial coefficient, (k_1 + k_2 + ... + k_m)! / (k_1! k_2! ... k_m!) // Complexity: O(sum(ks)) template <class Vec> static ModInt multinomial(const Vec &ks) { ModInt ret{1}; int sum = 0; for (int k : ks) { assert(k >= 0); ret *= ModInt(k).facinv(), sum += k; } return ret * ModInt(sum).fac(); } // Catalan number, C_n = binom(2n, n) / (n + 1) // C_0 = 1, C_1 = 1, C_2 = 2, C_3 = 5, C_4 = 14, ... // https://oeis.org/A000108 // Complexity: O(n) static ModInt catalan(int n) { if (n < 0) return ModInt(0); return ModInt(n * 2).fac() * ModInt(n + 1).facinv() * ModInt(n).facinv(); } ModInt sqrt() const { if (val_ == 0) return 0; if (md == 2) return val_; if (pow((md - 1) / 2) != 1) return 0; ModInt b = 1; while (b.pow((md - 1) / 2) == 1) b += 1; int e = 0, m = md - 1; while (m % 2 == 0) m >>= 1, e++; ModInt x = pow((m - 1) / 2), y = (*this) * x * x; x *= (*this); ModInt z = b.pow(m); while (y != 1) { int j = 0; ModInt t = y; while (t != 1) j++, t *= t; z = z.pow(1LL << (e - j - 1)); x *= z, z *= z, y *= z; e = j; } return ModInt(std::min(x.val_, md - x.val_)); } }; template <int md> std::vector<ModInt<md>> ModInt<md>::facs = {1}; template <int md> std::vector<ModInt<md>> ModInt<md>::facinvs = {1}; template <int md> std::vector<ModInt<md>> ModInt<md>::invs = {0}; using mint = ModInt<998244353>; #include <chrono> #include <utility> #include <vector> // Tree isomorphism with hashing (ハッシュによる木の同型判定) // Dependence: ModInt or ModIntRuntime // Reference: https://snuke.hatenablog.com/entry/2017/02/03/054210 // Verified: https://atcoder.jp/contests/nikkei2019-2-final/submissions/9044698 (ModInt) // https://atcoder.jp/contests/nikkei2019-2-final/submissions/9044745 (ModIntRuntime) template <typename ModInt> struct tree_isomorphism { using DoubleHash = std::pair<ModInt, ModInt>; using Edges = std::vector<std::vector<int>>; // vector<set<int>>; int V; Edges e; tree_isomorphism(int v) : V(v), e(v) {} void add_edge(int u, int v) { e[u].emplace_back(v); e[v].emplace_back(u); } static uint64_t splitmix64(uint64_t x) { // https://codeforces.com/blog/entry/62393 http://xorshift.di.unimi.it/splitmix64.c x += 0x9e3779b97f4a7c15; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return x ^ (x >> 31); } DoubleHash get_hash(DoubleHash x) const { static const uint64_t FIXED_RANDOM = std::chrono::steady_clock::now().time_since_epoch().count(); return {splitmix64(x.first.val() + FIXED_RANDOM), splitmix64(x.second.val() + FIXED_RANDOM)}; } static void add_hash(DoubleHash &l, const DoubleHash &r) { l.first += r.first, l.second += r.second; } static DoubleHash subtract_hash(const DoubleHash &l, const DoubleHash &r) { return {l.first - r.first, l.second - r.second}; } std::vector<DoubleHash> hash; // hash of the tree, each node regarded as root std::vector<DoubleHash> hash_subtree; // hash of the subtree std::vector<DoubleHash> hash_par; // hash of the subtree whose root is parent[i], not containing i DoubleHash hash_p; // \in [1, hmod), should be set randomly DoubleHash hash_dfs1_(int now, int prv) { hash_subtree[now] = hash_p; for (auto nxt : e[now]) { if (nxt != prv) add_hash(hash_subtree[now], hash_dfs1_(nxt, now)); } return get_hash(hash_subtree[now]); } void hash_dfs2_(int now, int prv) { add_hash(hash[now], hash_subtree[now]); if (prv >= 0) hash_par[now] = subtract_hash(hash[prv], get_hash(hash_subtree[now])); for (auto nxt : e[now]) if (nxt != prv) { DoubleHash tmp = subtract_hash(hash[now], get_hash(hash_subtree[nxt])); add_hash(hash[nxt], get_hash(tmp)); hash_dfs2_(nxt, now); } } void build_hash(int root, int p1, int p2) { hash_p = std::make_pair(p1, p2); hash.resize(V), hash_subtree.resize(V), hash_par.resize(V); hash_dfs1_(root, -1); hash_dfs2_(root, -1); } }; void NG() { cout << "No" << '\n'; } #include <cassert> #include <iostream> #include <vector> // Bipartite matching of undirected bipartite graph (Hopcroft-Karp) // https://ei1333.github.io/luzhiled/snippets/graph/hopcroft-karp.html // Complexity: O((V + E)sqrtV) // int solve(): enumerate maximum number of matching / return -1 (if graph is not bipartite) struct BipartiteMatching { int V; std::vector<std::vector<int>> to; // Adjacency list std::vector<int> dist; // dist[i] = (Distance from i'th node) std::vector<int> match; // match[i] = (Partner of i'th node) or -1 (No partner) std::vector<int> used, vv; std::vector<int> color; // color of each node(checking bipartition): 0/1/-1(not determined) BipartiteMatching() = default; BipartiteMatching(int V_) : V(V_), to(V_), match(V_, -1), used(V_), color(V_, -1) {} void add_edge(int u, int v) { assert(u >= 0 and u < V and v >= 0 and v < V and u != v); to[u].push_back(v); to[v].push_back(u); } void _bfs() { dist.assign(V, -1); std::vector<int> q; int lq = 0; for (int i = 0; i < V; i++) { if (!color[i] and !used[i]) q.push_back(i), dist[i] = 0; } while (lq < int(q.size())) { int now = q[lq++]; for (auto nxt : to[now]) { int c = match[nxt]; if (c >= 0 and dist[c] == -1) q.push_back(c), dist[c] = dist[now] + 1; } } } bool _dfs(int now) { vv[now] = true; for (auto nxt : to[now]) { int c = match[nxt]; if (c < 0 or (!vv[c] and dist[c] == dist[now] + 1 and _dfs(c))) { match[nxt] = now, match[now] = nxt; used[now] = true; return true; } } return false; } bool _color_bfs(int root) { color[root] = 0; std::vector<int> q{root}; int lq = 0; while (lq < int(q.size())) { int now = q[lq++], c = color[now]; for (auto nxt : to[now]) { if (color[nxt] == -1) { color[nxt] = !c, q.push_back(nxt); } else if (color[nxt] == c) { return false; } } } return true; } int solve() { for (int i = 0; i < V; i++) { if (color[i] == -1 and !_color_bfs(i)) return -1; } int ret = 0; while (true) { _bfs(); vv.assign(V, false); int flow = 0; for (int i = 0; i < V; i++) { if (!color[i] and !used[i] and _dfs(i)) flow++; } if (!flow) break; ret += flow; } return ret; } template <class OStream> friend OStream &operator<<(OStream &os, const BipartiteMatching &bm) { os << "{N=" << bm.V << ':'; for (int i = 0; i < bm.V; i++) { if (bm.match[i] > i) os << '(' << i << '-' << bm.match[i] << "),"; } return os << '}'; } }; #include <algorithm> #include <cassert> #include <vector> // Directed graph library to find strongly connected components (強連結成分分解) // 0-indexed directed graph // Complexity: O(V + E) struct DirectedGraphSCC { int V; // # of Vertices std::vector<std::vector<int>> to, from; std::vector<int> used; // Only true/false std::vector<int> vs; std::vector<int> cmp; int scc_num = -1; DirectedGraphSCC(int V = 0) : V(V), to(V), from(V), cmp(V) {} void _dfs(int v) { used[v] = true; for (auto t : to[v]) if (!used[t]) _dfs(t); vs.push_back(v); } void _rdfs(int v, int k) { used[v] = true; cmp[v] = k; for (auto t : from[v]) if (!used[t]) _rdfs(t, k); } void add_edge(int from_, int to_) { assert(from_ >= 0 and from_ < V and to_ >= 0 and to_ < V); to[from_].push_back(to_); from[to_].push_back(from_); } // Detect strongly connected components and return # of them. // Also, assign each vertex `v` the scc id `cmp[v]` (0-indexed) int FindStronglyConnectedComponents() { used.assign(V, false); vs.clear(); for (int v = 0; v < V; v++) if (!used[v]) _dfs(v); used.assign(V, false); scc_num = 0; for (int i = (int)vs.size() - 1; i >= 0; i--) if (!used[vs[i]]) _rdfs(vs[i], scc_num++); return scc_num; } // Find and output the vertices that form a closed cycle. // output: {v_1, ..., v_C}, where C is the length of cycle, // {} if there's NO cycle (graph is DAG) int _c, _init; std::vector<int> _ret_cycle; bool _dfs_detectcycle(int now, bool b0) { if (now == _init and b0) return true; for (auto nxt : to[now]) if (cmp[nxt] == _c and !used[nxt]) { _ret_cycle.emplace_back(nxt), used[nxt] = 1; if (_dfs_detectcycle(nxt, true)) return true; _ret_cycle.pop_back(); } return false; } std::vector<int> DetectCycle() { int ns = FindStronglyConnectedComponents(); if (ns == V) return {}; std::vector<int> cnt(ns); for (auto x : cmp) cnt[x]++; _c = std::find_if(cnt.begin(), cnt.end(), [](int x) { return x > 1; }) - cnt.begin(); _init = std::find(cmp.begin(), cmp.end(), _c) - cmp.begin(); used.assign(V, false); _ret_cycle.clear(); _dfs_detectcycle(_init, false); return _ret_cycle; } // After calling `FindStronglyConnectedComponents()`, generate a new graph by uniting all // vertices belonging to the same component(The resultant graph is DAG). DirectedGraphSCC GenerateTopologicalGraph() { DirectedGraphSCC newgraph(scc_num); for (int s = 0; s < V; s++) for (auto t : to[s]) { if (cmp[s] != cmp[t]) newgraph.add_edge(cmp[s], cmp[t]); } return newgraph; } }; #include <cassert> #include <utility> #include <vector> // Dulmage–Mendelsohn (DM) decomposition (DM 分解) // return: [(W+0, W-0), (W+1,W-1),...,(W+(k+1), W-(k+1))] // : sequence of pair (left vetrices, right vertices) // - |W+0| < |W-0| or both empty // - |W+i| = |W-i| (i = 1, ..., k) // - |W+(k+1)| > |W-(k+1)| or both empty // - W is topologically sorted // Example: // (2, 2, [(0,0), (0,1), (1,0)]) => [([],[]),([0,],[1,]),([1,],[0,]),([],[]),] // Complexity: O(N + (N + M) sqrt(N)) // Verified: https://yukicoder.me/problems/no/1615 std::vector<std::pair<std::vector<int>, std::vector<int>>> dulmage_mendelsohn(int L, int R, const std::vector<std::pair<int, int>> &edges) { for (auto p : edges) { assert(0 <= p.first and p.first < L); assert(0 <= p.second and p.second < R); } BipartiteMatching bm(L + R); for (auto p : edges) bm.add_edge(p.first, L + p.second); bm.solve(); DirectedGraphSCC scc(L + R); for (auto p : edges) scc.add_edge(p.first, L + p.second); for (int l = 0; l < L; ++l) { if (bm.match[l] >= L) scc.add_edge(bm.match[l], l); } int nscc = scc.FindStronglyConnectedComponents(); std::vector<int> cmp_map(nscc, -2); std::vector<int> vis(L + R); std::vector<int> st; for (int c = 0; c < 2; ++c) { std::vector<std::vector<int>> to(L + R); auto color = [&L](int x) { return x >= L; }; for (auto p : edges) { int u = p.first, v = L + p.second; if (color(u) != c) std::swap(u, v); to[u].push_back(v); if (bm.match[u] == v) to[v].push_back(u); } for (int i = 0; i < L + R; ++i) { if (bm.match[i] >= 0 or color(i) != c or vis[i]) continue; vis[i] = 1, st = {i}; while (!st.empty()) { int now = st.back(); cmp_map[scc.cmp[now]] = c - 1; st.pop_back(); for (int nxt : to[now]) { if (!vis[nxt]) vis[nxt] = 1, st.push_back(nxt); } } } } int nset = 1; for (int n = 0; n < nscc; ++n) { if (cmp_map[n] == -2) cmp_map[n] = nset++; } for (auto &x : cmp_map) { if (x == -1) x = nset; } nset++; std::vector<std::pair<std::vector<int>, std::vector<int>>> groups(nset); for (int l = 0; l < L; ++l) { if (bm.match[l] < 0) continue; int c = cmp_map[scc.cmp[l]]; groups[c].first.push_back(l); groups[c].second.push_back(bm.match[l] - L); } for (int l = 0; l < L; ++l) { if (bm.match[l] >= 0) continue; int c = cmp_map[scc.cmp[l]]; groups[c].first.push_back(l); } for (int r = 0; r < R; ++r) { if (bm.match[L + r] >= 0) continue; int c = cmp_map[scc.cmp[L + r]]; groups[c].second.push_back(r); } return groups; } void solve() { int N; cin >> N; dbg(N); vector<vector<pint>> to(N); int wsum = 0; vector<int> deg(N); vector<pint> edges; int h = N; REP(e, N - 1) { int u, v, w; cin >> u >> v >> w; --u, --v; deg.at(u)++; deg.at(v)++; to.at(u).emplace_back(v, w); to.at(v).emplace_back(u, w); wsum += w; int a = u; REP(_, w - 1) { edges.emplace_back(a, h); a = h; ++h; } edges.emplace_back(a, v); } dbg(edges); tree_isomorphism<mint> tree(h); shortest_path<int> sp1(h); for (auto [u, v] : edges) { tree.add_edge(u, v); sp1.add_bi_edge(u, v, 1); } int H, W; cin >> H >> W; vector<string> S(H); cin >> S; dbg(S); if (wsum > H * W) { NG(); return; } vector<pint> vs; map<pint, int> v2i; REP(x, H) REP(y, W) { if (S.at(x).at(y) == '#') { v2i[{x, y}] = vs.size(); vs.emplace_back(x, y); } } if (vs.size() != h) { NG(); return; } tree_isomorphism<mint> tree2(vs.size()); shortest_path<int> sp2(h); for (auto [x, y] : vs) { for (auto [x2, y2] : vs) { if (pint(x, y) < pint(x2, y2)) { if (abs(x - x2) + abs(y - y2) == 1) { tree2.add_edge(v2i[{x, y}], v2i[{x2, y2}]); sp2.add_bi_edge(v2i[{x, y}], v2i[{x2, y2}], 1); } } } } constexpr int P1 = 13497, P2 = 98715397; tree.build_hash(0, P1, P2); tree2.build_hash(0, P1, P2); vector d1(h, vector<int>(h)); vector d2(h, vector<int>(h)); REP(i, h) { sp1.solve(i); sp2.solve(i); d1.at(i) = sp1.dist; d2.at(i) = sp2.dist; } // dbg(tree.hash); // dbg(tree2.hash); { auto st1 = tree.hash, st2 = tree2.hash; sort(ALL(st1)), sort(ALL(st2)); if (st1 != st2) { NG(); return; } } // vector<pint> ret(h, pint(-1, -1)); vector<int> mate(h, -1), mateinv(h, -1); set<pint> fixed_pairs; while ((int)fixed_pairs.size() < h) { dbg(mate); dbg(mateinv); dbg(fixed_pairs); vector<pint> es{fixed_pairs.begin(), fixed_pairs.end()}; REP(i, h) REP(j, h) { if (mate.at(i) >= 0) continue; if (mateinv.at(j) >= 0) continue; if (tree.hash.at(i) != tree2.hash.at(j)) continue; bool failure = false; for (auto [x, y] : fixed_pairs) { if (d1.at(x).at(i) != d2.at(y).at(j)) { failure = true; break; } } if (failure) continue; es.emplace_back(i, j); } auto dm = dulmage_mendelsohn(h, h, es); dbg(dm); bool upd = false; for (auto [l, r] : dm) { if (l.size() == 1 and r.size() == 1) { int i = l.at(0), j = r.at(0); if (mate.at(i) < 0) { mate.at(i) = j; mateinv.at(j) = i; fixed_pairs.emplace(i, j); upd = true; } } } if (!upd) { for (auto [l, r] : dm) { if (l.size() <= 1) continue; int i = l.at(0); int j = r.at(0); mate.at(i) = j; mateinv.at(j) = i; fixed_pairs.emplace(i, j); break; } } } cout << "Yes\n"; REP(i, N) { auto [x, y] = vs.at(mate.at(i)); cout << x + 1 << " " << y + 1 << '\n'; } } int main() { int Q; cin >> Q; while (Q--) solve(); }