結果
問題 |
No.2507 Yet Another Subgraph Counting
|
ユーザー |
|
提出日時 | 2023-09-11 16:29:50 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,578 bytes |
コンパイル時間 | 3,123 ms |
コンパイル使用メモリ | 117,848 KB |
最終ジャッジ日時 | 2025-02-16 21:38:33 |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 36 RE * 14 TLE * 2 |
ソースコード
#include <cassert> #include <iostream> #include <utility> #include <vector> using vertex = size_t; using vertex_set = size_t; using edge = std::pair<vertex, vertex>; using edge_set = size_t; #include <atcoder/dsu> uint32_t naive(const size_t n, const size_t m, const std::vector<edge> &edges) { assert(m < 24); std::vector<std::vector<edge_set>> cycles(n); for (edge_set s = 0; s < 1u << m; ++s) { atcoder::dsu uf(n); std::vector<size_t> deg(n); for (size_t i = 0; i < m; ++i) if ((s >> i) & 1) { const auto &[u, v] = edges[i]; ++deg[u], ++deg[v]; uf.merge(u, v); } bool is_cycle = true; std::vector<vertex> vs; for (vertex v = 0; v < n; ++v) { if (deg[v] == 2) vs.push_back(v); else is_cycle &= deg[v] == 0; } for (size_t i = 1; i < vs.size(); ++i) { is_cycle &= uf.same(vs[i - 1], vs[i]); } if (is_cycle) for (vertex v : vs) cycles[v].push_back(s); } uint32_t ans = 0; for (edge_set s = 0; s < 1u << m; ++s) { bool ok = true; for (vertex v = 0; v < n; ++v) { size_t cycle_count = 0; for (edge_set c : cycles[v]) cycle_count += (c & s) == c; ok &= cycle_count <= 1; } ans += ok; } return ans; } int main() { size_t n, m; std::cin >> n >> m; std::vector<edge> edges(m); for (auto &[u, v] : edges) { std::cin >> u >> v; --u, --v; } std::cout << naive(n, m, edges) << '\n'; }