結果

問題 No.2507 Yet Another Subgraph Counting
ユーザー suisensuisen
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

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

#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';
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0