結果

問題 No.2507 Yet Another Subgraph Counting
ユーザー emthrm
提出日時 2023-08-27 13:38:51
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 3,621 bytes
コンパイル時間 1,295 ms
コンパイル使用メモリ 111,216 KB
実行使用メモリ 13,636 KB
最終ジャッジ日時 2024-12-27 10:33:46
合計ジャッジ時間 42,883 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 39 TLE * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <algorithm>
#include <cassert>
#include <concepts>
#include <cstdint>
#include <iostream>
#include <utility>
#include <vector>

namespace emthrm {

std::vector<int> detect_path(const std::vector<std::vector<int>>& graph,
                             const int s, const int t) {
  std::vector<bool> is_visited(graph.size(), false);
  std::vector<int> path{s};
  const auto dfs = [&graph, t, &is_visited, &path](auto dfs, const int ver)
      -> bool {
    if (ver == t) return true;
    is_visited[ver] = true;
    for (const int e : graph[ver]) {
      if (!is_visited[e]) {
        path.emplace_back(e);
        if (dfs(dfs, e)) return true;
        path.pop_back();
      }
    }
    return false;
  };
  return dfs(dfs, s) ? path : std::vector<int>{};
}


struct UndoableUnionFind {
  explicit UndoableUnionFind(const int n) : data(n, -1) {}

  int root(const int ver) const {
    return data[ver] < 0 ? ver : root(data[ver]);
  }

  bool unite(int u, int v) {
    u = root(u);
    history.emplace_back(u, data[u]);
    v = root(v);
    history.emplace_back(v, data[v]);
    if (u == v) return false;
    if (data[u] > data[v]) std::swap(u, v);
    data[u] += data[v];
    data[v] = u;
    return true;
  }

  bool is_same(const int u, const int v) const { return root(u) == root(v); }

  int size(const int ver) const { return -data[root(ver)]; }

  void undo() {
    for (int i = 0; i < 2; ++i) {
      data[history.back().first] = history.back().second;
      history.pop_back();
    }
  }

  void snapshot() { history.clear(); }

  void rollback() {
    while (!history.empty()) undo();
  }

 private:
  std::vector<int> data;
  std::vector<std::pair<int, int>> history;
};

}  // namespace emthrm

bool KthBit(const std::integral auto bit_field, const int k) {
  return std::cmp_equal(bit_field >> k & 1, 1);
}

// <TLE>
// 辺の塗り方をすべて試す。
int main() {
  constexpr int kMaxN = 13;

  int n, m;
  std::cin >> n >> m;
  assert(2 <= n && n <= kMaxN && 1 <= m && m <= n * (n - 1) / 2);
  std::vector<int> u(m), v(m);
  for (int i = 0; i < m; ++i) {
    std::cin >> u[i] >> v[i];
    assert(1 <= u[i] && u[i] < v[i] && v[i] <= n);
    --u[i]; --v[i];
  }

  const auto dfs = [m, &u, &v](
      auto dfs, const int index, uint32_t is_in_cycle, std::vector<std::vector<int>>* red_graph,
      emthrm::UndoableUnionFind* union_find) -> std::int64_t {
    if (index == m) return 1;
    std::int64_t ans = dfs(dfs, index + 1, is_in_cycle, red_graph, union_find);
    const bool is_united = union_find->unite(u[index], v[index]);
    if (!is_united) {
      if (KthBit(is_in_cycle, u[index]) || KthBit(is_in_cycle, v[index])) {
        union_find->undo();
        return ans;
      }
      const std::vector<int> cycle =
          emthrm::detect_path(*red_graph, u[index], v[index]);
      if (std::ranges::any_of(cycle,
                              [is_in_cycle](const int vertex) -> bool {
                                return KthBit(is_in_cycle, vertex);
                              })) {
        union_find->undo();
        return ans;
      }
      for (const int vertex : cycle) is_in_cycle |= UINT32_C(1) << vertex;
    }
    (*red_graph)[u[index]].emplace_back(v[index]);
    (*red_graph)[v[index]].emplace_back(u[index]);
    ans += dfs(dfs, index + 1, is_in_cycle, red_graph, union_find);
    (*red_graph)[u[index]].pop_back();
    (*red_graph)[v[index]].pop_back();
    union_find->undo();
    return ans;
  };
  std::vector<std::vector<int>> red_graph(n);
  emthrm::UndoableUnionFind union_find(n);
  std::cout << dfs(dfs, 0, 0, &red_graph, &union_find) << '\n';
  return 0;
}
0