cp-library-cpp
This documentation is automatically generated by online-judge-tools/verification-helper
test/src/graph/tree_decomposition_tw2_dp/AOJ2405.test.cpp
- View this file on GitHub
- Last update: 2022-11-01 16:55:57+09:00
- Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2405&lang=jp
Depends on
- Tree Decomposition Tw2
(library/graph/tree_decomposition_tw2.hpp)
- Tree Decomposition Tw2 Dp
(library/graph/tree_decomposition_tw2_dp.hpp)
Code
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2405&lang=jp"
#include <iostream>
#include <map>
#include <set>
constexpr int mod = 1000003;
#include "library/graph/tree_decomposition_tw2_dp.hpp"
using match = std::pair<int, int>;
using table_key = std::vector<match>;
using table_value = long long;
using table_entry = std::pair<table_key, table_value>;
using table = std::map<table_key, long long>;
struct state {
static constexpr int Forgotten = -2;
static constexpr int None = -1;
table mp;
};
void solve() {
using namespace suisen;
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, m;
std::cin >> n >> m;
if (n == 0 and m == 0) exit(0);
std::vector<std::set<int>> adj(n);
std::vector<std::pair<int, int>> edges;
for (int i = 0; i < n; ++i) {
edges.emplace_back(i, (i + 1) % n);
}
for (int i = 0; i < m; ++i) {
int u, v;
std::cin >> u >> v;
--u, --v;
edges.emplace_back(u, v);
}
for (const auto &[u, v] : edges) {
adj[u].insert(v);
adj[v].insert(u);
}
auto leaf = [&](const DecompNodeRooted&, int leaf_vertex) -> state {
return state { table{ table_entry{ table_key{ match{ leaf_vertex, state::None } }, table_value{ 1 } } } };
};
auto introduce = [&](const DecompNodeRooted&, const DecompNodeRooted&, const state& child_result, int introduce_vertex) -> state {
table ndp;
for (auto [matching, val] : child_result.mp) {
{
auto nxt_matching = matching;
nxt_matching.emplace_back(introduce_vertex, state::None);
std::sort(nxt_matching.begin(), nxt_matching.end());
ndp[nxt_matching] += val;
}
const int k = matching.size();
for (int i = 0; i < k; ++i) {
auto [u, v] = matching[i];
if (v != state::None or adj[introduce_vertex].find(u) == adj[introduce_vertex].end()) continue;
auto nxt_matching = matching;
nxt_matching[i].second = introduce_vertex;
nxt_matching.emplace_back(introduce_vertex, u);
std::sort(nxt_matching.begin(), nxt_matching.end());
ndp[nxt_matching] += val;
}
}
for (auto &[_, val] : ndp) val %= mod;
return state { ndp };
};
auto forget = [&](const DecompNodeRooted&, const DecompNodeRooted&, const state& child_result, int forget_vertex) -> state {
table ndp;
for (auto [matching, val] : child_result.mp) {
bool ok = true;
table_key nxt_matching;
for (auto [u, v] : matching) {
if (u == forget_vertex) {
ok &= v != state::None;
continue;
}
if (v == forget_vertex) {
nxt_matching.emplace_back(u, state::Forgotten);
} else {
nxt_matching.emplace_back(u, v);
}
}
if (not ok) {
continue;
}
std::sort(nxt_matching.begin(), nxt_matching.end());
ndp[nxt_matching] += val;
}
for (auto &[_, val] : ndp) val %= mod;
return state { ndp };
};
auto join = [&](const DecompNodeRooted&, const DecompNodeRooted&, const state& child_result_1, const DecompNodeRooted&, const state& child_result_2) -> state {
table ndp;
for (auto [matching1, val1] : child_result_1.mp) for (auto [matching2, val2] : child_result_2.mp) {
bool ok = true;
const int k = matching1.size();
table_key nxt_matching;
for (int i = 0; i < k; ++i) {
auto [u1, v1] = matching1[i];
auto [u2, v2] = matching2[i];
assert(u1 == u2);
if (v1 > v2) std::swap(v1, v2);
if (v1 == state::Forgotten) {
if (v2 == state::Forgotten) {
ok = false;
break;
} else if (v2 == state::None) {
nxt_matching.emplace_back(u1, v1);
} else {
ok = false;
break;
}
} else if (v1 == state::None) {
if (v2 == state::None) {
nxt_matching.emplace_back(u1, v1);
} else {
ok = false;
break;
}
} else {
if (v1 != v2) {
ok = false;
break;
} else {
nxt_matching.emplace_back(u1, v1);
}
}
if (not ok) break;
}
if (ok) {
std::sort(nxt_matching.begin(), nxt_matching.end());
ndp[nxt_matching] += val1 * val2;
}
}
for (auto &[_, val] : ndp) val %= mod;
return state { ndp };
};
state dp_root = NiceDecompTree(n, edges).run_dp<state>(leaf, introduce, forget, join);
long long ans = 0;
for (auto [matching, val] : dp_root.mp) {
bool ok = true;
for (auto &[u, v] : matching) {
if (v == state::None) {
ok = false;
break;
}
}
if (ok) {
ans += val;
}
}
std::cout << ans % mod << std::endl;
}
int main() {
while (true) solve();
}#line 1 "test/src/graph/tree_decomposition_tw2_dp/AOJ2405.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2405&lang=jp"
#include <iostream>
#include <map>
#include <set>
constexpr int mod = 1000003;
#line 1 "library/graph/tree_decomposition_tw2_dp.hpp"
#include <functional>
#line 1 "library/graph/tree_decomposition_tw2.hpp"
#include <algorithm>
#include <atcoder/dsu>
#include <cassert>
#include <deque>
#include <optional>
#include <utility>
#include <vector>
namespace suisen {
struct DecompNode {
std::vector<int> bag;
std::vector<int> adj;
};
struct DecompNodeRooted {
std::vector<int> bag;
int par;
std::vector<int> ch;
};
struct TreeDecompositionTW2 {
TreeDecompositionTW2(const int n = 0, const std::vector<std::pair<int, int>>& edges = {}) : _n(n), _edges(edges) {}
TreeDecompositionTW2(const std::vector<std::vector<int>>& g) : TreeDecompositionTW2(g.size()) {
for (int i = 0; i < _n; ++i) for (int j : g[i]) if (i < j) add_edge(i, j);
}
void add_edge(int u, int v) {
_edges.emplace_back(u, v);
}
std::optional<std::vector<DecompNode>> decomp() const {
std::vector<std::vector<std::pair<int, int>>> g(_n);
for (auto [u, v] : _edges) if (u != v) {
if (u > v) std::swap(u, v);
const int du = g[u].size(), dv = g[v].size();
g[u].emplace_back(v, dv);
g[v].emplace_back(u, du);
}
std::vector<int8_t> seen(_n, false);
std::deque<int> dq;
auto push_if_removable = [&](int i) {
if (g[i].size() > 2 or std::exchange(seen[i], true)) return;
if (g[i].size() == 2) dq.push_back(i);
else dq.push_front(i);
};
for (int i = 0; i < _n; ++i) push_if_removable(i);
std::vector<int> roots;
std::vector<std::pair<int, int>> edges;
edges.reserve(_n - 1);
std::vector<std::vector<int>> bag(_n);
std::vector<std::vector<int>> link(_n);
atcoder::dsu uf(_n);
for (int id = 0; id < _n; ++id) {
if (dq.empty()) return std::nullopt;
int u = dq.front();
dq.pop_front();
if (g[u].size() == 0) {
bag[id] = { u };
roots.push_back(id);
} else if (g[u].size() == 1) {
int v = remove_edge(g, u, 0);
push_if_removable(v);
bag[id] = { u, v };
link[v].push_back(id);
} else {
int v = remove_edge(g, u, 0);
int w = remove_edge(g, u, 0);
if (v > w) std::swap(v, w);
bag[id] = { u, v, w };
const int dv = g[v].size(), dw = g[w].size();
g[v].emplace_back(w, dw);
g[w].emplace_back(v, dv);
remove_multiedges(g, v, dv);
remove_multiedges(g, w, dw);
push_if_removable(v);
push_if_removable(w);
link[v].push_back(id);
link[w].push_back(id);
}
std::reverse(link[u].begin(), link[u].end());
for (int id2 : link[u]) if (not uf.same(id, id2)) {
edges.emplace_back(id, id2);
uf.merge(id, id2);
}
g[u].clear(), g[u].shrink_to_fit(), link[u].clear(), link[u].shrink_to_fit();
}
const int root_num = roots.size();
for (int i = 0; i < root_num - 1; ++i) {
edges.emplace_back(roots[i], roots[i + 1]);
}
std::vector<DecompNode> res(_n);
for (int i = 0; i < _n; ++i) {
res[i].bag = std::move(bag[i]);
std::sort(res[i].bag.begin(), res[i].bag.end());
}
for (auto& [i, j] : edges) {
res[i].adj.push_back(j);
res[j].adj.push_back(i);
}
return res;
}
std::optional<std::vector<DecompNodeRooted>> nice_decomp() const {
auto opt_decomp = decomp();
if (not opt_decomp.has_value()) return std::nullopt;
std::vector<DecompNodeRooted> res(_n);
for (int i = 0; i < _n; ++i) {
res[i].bag = std::move((*opt_decomp)[i].bag);
}
const int root = 0;
std::vector<std::vector<std::pair<int, int>>> adj_idx(_n);
for (int i = 0; i < _n; ++i) for (int j : (*opt_decomp)[i].adj) if (i < j) {
int u = i, v = j;
auto fix_deg = [&](int& z) {
if ((z == root) + adj_idx[z].size() != 3) return;
const int n = res.size();
const int idx_zw = 0;
const auto [w, idx_wz] = adj_idx[z][idx_zw];
auto& node = res.emplace_back();
node.bag = res[z].bag;
adj_idx.push_back({ { z, idx_zw }, { w, idx_wz } });
adj_idx[z][idx_zw] = { n, 0 };
adj_idx[w][idx_wz] = { n, 1 };
z = n;
};
fix_deg(u), fix_deg(v);
const int du = adj_idx[u].size(), dv = adj_idx[v].size();
adj_idx[u].emplace_back(v, dv);
adj_idx[v].emplace_back(u, du);
}
for (int i = 0; i < int(res.size()); ++i) {
res[i].ch.reserve(adj_idx[i].size());
for (auto [j, idx] : adj_idx[i]) res[i].ch.push_back(j);
adj_idx[i].clear(), adj_idx[i].shrink_to_fit();
}
adj_idx.clear(), adj_idx.shrink_to_fit();
std::deque<int> dq{ root };
while (dq.size()) {
int u = dq.front();
dq.pop_front();
for (int v : res[u].ch) {
res[v].par = u;
res[v].ch.erase(std::find(res[v].ch.begin(), res[v].ch.end(), u));
dq.push_back(v);
}
auto fix_path = [&](int u, int v) {
std::vector<int> dif;
std::set_difference(res[v].bag.begin(), res[v].bag.end(), res[u].bag.begin(), res[u].bag.end(), std::back_inserter(dif));
std::set_difference(res[u].bag.begin(), res[u].bag.end(), res[v].bag.begin(), res[v].bag.end(), std::back_inserter(dif));
assert(dif.size());
res[u].ch.erase(std::find(res[u].ch.begin(), res[u].ch.end(), v));
while (dif.size() > 1) {
const int n = res.size();
auto& node = res.emplace_back();
std::set_symmetric_difference(res[u].bag.begin(), res[u].bag.end(), std::prev(dif.end()), dif.end(), std::back_inserter(node.bag));
res[u].ch.push_back(n);
dif.pop_back();
node.par = u;
u = n;
}
res[u].ch.push_back(v);
res[v].par = u;
};
if (res[u].ch.size() == 2) {
for (int v : res[u].ch) if (res[u].bag != res[v].bag) {
const int n = res.size();
*std::find(res[u].ch.begin(), res[u].ch.end(), v) = n;
auto& node = res.emplace_back();
node.bag = res[u].bag;
node.ch = { v };
node.par = u;
fix_path(n, v);
}
} else if (res[u].ch.size() == 1) {
fix_path(u, res[u].ch[0]);
} else if (res[u].ch.size() == 0) {
while (res[u].bag.size() > 1) {
const int n = res.size();
auto& node = res.emplace_back();
node.bag = std::vector<int>(res[u].bag.begin(), std::prev(res[u].bag.end()));
node.par = u;
res[u].ch.push_back(n);
u = n;
}
} else {
assert(false);
}
}
res[root].par = -1;
return res;
}
static void assert_nice(const std::vector<DecompNodeRooted>& nodes, int root) {
auto dfs = [&](auto dfs, int u) -> void {
for (int v : nodes[u].ch) dfs(dfs, v);
assert(nodes[u].ch.size() <= 2);
if (nodes[u].ch.size() == 2) {
int x = nodes[u].ch[0], y = nodes[u].ch[1];
assert(nodes[u].bag == nodes[x].bag and nodes[u].bag == nodes[y].bag);
} else if (nodes[u].ch.size() == 1) {
int x = nodes[u].ch[0];
std::vector<int> d;
std::set_symmetric_difference(nodes[u].bag.begin(), nodes[u].bag.end(), nodes[x].bag.begin(), nodes[x].bag.end(), std::back_inserter(d));
assert(d.size() == 1);
} else {
assert(nodes[u].bag.size() == 1);
}
};
dfs(dfs, root);
}
private:
int _n;
std::vector<std::pair<int, int>> _edges;
static int remove_edge(std::vector<std::vector<std::pair<int, int>>>& g, int u, int idx_uv) {
auto [v, idx_vu] = g[u][idx_uv];
if (idx_vu != int(g[v].size()) - 1) {
auto [w, idx_wv] = g[v].back();
std::swap(g[v][idx_vu], g[v].back());
g[w][idx_wv].second = idx_vu;
}
g[v].pop_back();
if (idx_uv != int(g[u].size()) - 1) {
auto [z, idx_zu] = g[u].back();
std::swap(g[u][idx_uv], g[u].back());
g[z][idx_zu].second = idx_uv;
}
g[u].pop_back();
remove_multiedges(g, v, idx_vu);
remove_multiedges(g, u, idx_uv);
return v;
}
static void remove_multiedges(std::vector<std::vector<std::pair<int, int>>>& g, int u, int idx_uv) {
auto is_unnecessary = [&](int idx_uv) {
const int du = int(g[u].size());
if (idx_uv >= du) return false;
if (idx_uv + 1 < du and g[u][idx_uv].first == g[u][idx_uv + 1].first) return true;
if (idx_uv + 2 < du and g[u][idx_uv].first == g[u][idx_uv + 2].first) return true;
if (idx_uv - 1 >= 0 and g[u][idx_uv].first == g[u][idx_uv - 1].first) return true;
if (idx_uv - 2 >= 0 and g[u][idx_uv].first == g[u][idx_uv - 2].first) return true;
return false;
};
while (is_unnecessary(idx_uv)) remove_edge(g, u, idx_uv);
}
};
} // namespace suisen
#line 7 "library/graph/tree_decomposition_tw2_dp.hpp"
namespace suisen {
enum class NodeType {
LEAF,
INTRODUCE,
FORGET,
JOIN
};
struct NiceDecompTree {
static constexpr int root = 0;
NiceDecompTree() = default;
NiceDecompTree(std::vector<DecompNodeRooted>&& nodes) : _n(nodes.size()), _nodes(std::move(nodes)), _pst(_n, -1) {}
NiceDecompTree(const std::vector<DecompNodeRooted>& nodes) : _n(nodes.size()), _nodes(nodes), _pst(_n, -1) {}
NiceDecompTree(int n, const std::vector<std::pair<int, int>>& edges) : NiceDecompTree(*TreeDecompositionTW2{ n, edges }.nice_decomp()) {}
NiceDecompTree(const std::vector<std::vector<int>>& g) : NiceDecompTree(*TreeDecompositionTW2{ g }.nice_decomp()) {}
int size() const { return _n; }
NodeType get_node_type(int i) const {
if (_nodes[i].ch.size() == 0) return NodeType::LEAF;
if (_nodes[i].ch.size() == 2) return NodeType::JOIN;
if (_nodes[i].bag.size() > _nodes[_nodes[i].ch[0]].bag.size()) return NodeType::INTRODUCE;
return NodeType::FORGET;
}
std::vector<NodeType> get_node_types() const {
std::vector<NodeType> types(_n);
for (int i = 0; i < _n; ++i) types[i] = get_node_type(i);
return types;
}
const DecompNodeRooted& operator[](int i) const { return _nodes[i]; }
DecompNodeRooted& operator[](int i) { return _nodes[i]; }
template <typename T> T run_dp(
std::function<T(const DecompNodeRooted& node, int leaf_vertex)> leaf,
std::function<T(const DecompNodeRooted& node, const DecompNodeRooted& child_node, const T& child_result, int introduce_vertex)> introduce,
std::function<T(const DecompNodeRooted& node, const DecompNodeRooted& child_node, const T& child_result, int forget_vertex)> forget,
std::function<T(const DecompNodeRooted& node, const DecompNodeRooted& child_node_1, const T& child_result_1, const DecompNodeRooted& child_node_2, const T& child_result_2)> join
) const {
prepare_post_order();
std::vector<T> dp(_n);
for (int i : _pst) {
dp[i] = [&, this] {
switch (get_node_type(i)) {
case NodeType::LEAF:
{
return leaf(_nodes[i], _nodes[i].bag[0]);
}
case NodeType::INTRODUCE:
{
int j = _nodes[i].ch[0];
int sj = _nodes[j].bag.size();
int v = _nodes[i].bag[sj];
for (int k = 0; k < sj; ++k) if (_nodes[i].bag[k] != _nodes[j].bag[k]) {
v = _nodes[i].bag[k];
break;
}
return introduce(_nodes[i], _nodes[j], dp[j], v);
}
case NodeType::FORGET:
{
int j = _nodes[i].ch[0];
int si = _nodes[i].bag.size();
int v = _nodes[j].bag[si];
for (int k = 0; k < si; ++k) if (_nodes[i].bag[k] != _nodes[j].bag[k]) {
v = _nodes[j].bag[k];
break;
}
return forget(_nodes[i], _nodes[j], dp[j], v);
}
case NodeType::JOIN:
{
int j = _nodes[i].ch[0], k = _nodes[i].ch[1];
return join(_nodes[i], _nodes[j], dp[j], _nodes[k], dp[k]);
}
default:
{
assert(false);
}
}
}();
}
return dp[root];
}
private:
int _n;
std::vector<DecompNodeRooted> _nodes;
mutable std::vector<int> _pst;
void prepare_post_order() const {
if (_pst.empty() or _pst.front() >= 0) return;
auto it = _pst.begin();
std::vector<std::size_t> eid(_n, 0);
for (int cur = root; cur >= 0;) {
if (eid[cur] == _nodes[cur].ch.size()) {
*it++ = cur;
cur = _nodes[cur].par;
} else {
cur = _nodes[cur].ch[eid[cur]++];
}
}
}
};
} // namespace suisen
#line 10 "test/src/graph/tree_decomposition_tw2_dp/AOJ2405.test.cpp"
using match = std::pair<int, int>;
using table_key = std::vector<match>;
using table_value = long long;
using table_entry = std::pair<table_key, table_value>;
using table = std::map<table_key, long long>;
struct state {
static constexpr int Forgotten = -2;
static constexpr int None = -1;
table mp;
};
void solve() {
using namespace suisen;
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, m;
std::cin >> n >> m;
if (n == 0 and m == 0) exit(0);
std::vector<std::set<int>> adj(n);
std::vector<std::pair<int, int>> edges;
for (int i = 0; i < n; ++i) {
edges.emplace_back(i, (i + 1) % n);
}
for (int i = 0; i < m; ++i) {
int u, v;
std::cin >> u >> v;
--u, --v;
edges.emplace_back(u, v);
}
for (const auto &[u, v] : edges) {
adj[u].insert(v);
adj[v].insert(u);
}
auto leaf = [&](const DecompNodeRooted&, int leaf_vertex) -> state {
return state { table{ table_entry{ table_key{ match{ leaf_vertex, state::None } }, table_value{ 1 } } } };
};
auto introduce = [&](const DecompNodeRooted&, const DecompNodeRooted&, const state& child_result, int introduce_vertex) -> state {
table ndp;
for (auto [matching, val] : child_result.mp) {
{
auto nxt_matching = matching;
nxt_matching.emplace_back(introduce_vertex, state::None);
std::sort(nxt_matching.begin(), nxt_matching.end());
ndp[nxt_matching] += val;
}
const int k = matching.size();
for (int i = 0; i < k; ++i) {
auto [u, v] = matching[i];
if (v != state::None or adj[introduce_vertex].find(u) == adj[introduce_vertex].end()) continue;
auto nxt_matching = matching;
nxt_matching[i].second = introduce_vertex;
nxt_matching.emplace_back(introduce_vertex, u);
std::sort(nxt_matching.begin(), nxt_matching.end());
ndp[nxt_matching] += val;
}
}
for (auto &[_, val] : ndp) val %= mod;
return state { ndp };
};
auto forget = [&](const DecompNodeRooted&, const DecompNodeRooted&, const state& child_result, int forget_vertex) -> state {
table ndp;
for (auto [matching, val] : child_result.mp) {
bool ok = true;
table_key nxt_matching;
for (auto [u, v] : matching) {
if (u == forget_vertex) {
ok &= v != state::None;
continue;
}
if (v == forget_vertex) {
nxt_matching.emplace_back(u, state::Forgotten);
} else {
nxt_matching.emplace_back(u, v);
}
}
if (not ok) {
continue;
}
std::sort(nxt_matching.begin(), nxt_matching.end());
ndp[nxt_matching] += val;
}
for (auto &[_, val] : ndp) val %= mod;
return state { ndp };
};
auto join = [&](const DecompNodeRooted&, const DecompNodeRooted&, const state& child_result_1, const DecompNodeRooted&, const state& child_result_2) -> state {
table ndp;
for (auto [matching1, val1] : child_result_1.mp) for (auto [matching2, val2] : child_result_2.mp) {
bool ok = true;
const int k = matching1.size();
table_key nxt_matching;
for (int i = 0; i < k; ++i) {
auto [u1, v1] = matching1[i];
auto [u2, v2] = matching2[i];
assert(u1 == u2);
if (v1 > v2) std::swap(v1, v2);
if (v1 == state::Forgotten) {
if (v2 == state::Forgotten) {
ok = false;
break;
} else if (v2 == state::None) {
nxt_matching.emplace_back(u1, v1);
} else {
ok = false;
break;
}
} else if (v1 == state::None) {
if (v2 == state::None) {
nxt_matching.emplace_back(u1, v1);
} else {
ok = false;
break;
}
} else {
if (v1 != v2) {
ok = false;
break;
} else {
nxt_matching.emplace_back(u1, v1);
}
}
if (not ok) break;
}
if (ok) {
std::sort(nxt_matching.begin(), nxt_matching.end());
ndp[nxt_matching] += val1 * val2;
}
}
for (auto &[_, val] : ndp) val %= mod;
return state { ndp };
};
state dp_root = NiceDecompTree(n, edges).run_dp<state>(leaf, introduce, forget, join);
long long ans = 0;
for (auto [matching, val] : dp_root.mp) {
bool ok = true;
for (auto &[u, v] : matching) {
if (v == state::None) {
ok = false;
break;
}
}
if (ok) {
ans += val;
}
}
std::cout << ans % mod << std::endl;
}
int main() {
while (true) solve();
}