結果
問題 | No.2507 Yet Another Subgraph Counting |
ユーザー |
|
提出日時 | 2023-08-21 04:24:48 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,584 bytes |
コンパイル時間 | 1,063 ms |
コンパイル使用メモリ | 89,192 KB |
実行使用メモリ | 13,640 KB |
最終ジャッジ日時 | 2024-12-14 12:58:03 |
合計ジャッジ時間 | 21,424 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 36 TLE * 6 WA * 10 |
ソースコード
#include <cassert>#include <iostream>#include <utility>#include <vector>using vertex = size_t;using vertex_set = size_t;using edge = std::pair<vertex, vertex>;#include <atcoder/dsu>uint32_t naive(const size_t n, const size_t m, const std::vector<edge> &edges) {assert(m < 1u << 24);using edge_set = size_t;std::vector<std::vector<size_t>> 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 (size_t 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';}