数学/基底
(test/math/basis.test.cpp)

• View this file on GitHub
• Last update: 2023-02-25 01:48:23+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2416

Depends on

• 辺 (include/emthrm/graph/edge.hpp)
• 基底 (basis) (include/emthrm/math/basis.hpp)

Code

/*
 * @title 数学/基底
 *
 * verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2416
 */

#include <bitset>
#include <iostream>
#include <vector>

#include "emthrm/graph/edge.hpp"
#include "emthrm/math/basis.hpp"

int main() {
  constexpr int D = 60;
  int n, m, q;
  std::cin >> n >> m >> q;
  std::vector<std::vector<emthrm::Edge<long long>>> graph(n);
  while (m--) {
    int f, t;
    long long p;
    std::cin >> f >> t >> p;
    graph[f].emplace_back(f, t, p);
    graph[t].emplace_back(t, f, p);
  }
  std::vector<long long> x(n, -1);
  x[0] = 0;
  emthrm::Basis<D> basis;
  const auto dfs = [&graph, &x, &basis](auto dfs, const int par, const int ver)
      -> void {
    for (const emthrm::Edge<long long>& e : graph[ver]) {
      if (e.dst != par) {
        if (x[e.dst] == -1) {
          x[e.dst] = x[ver] ^ e.cost;
          dfs(dfs, ver, e.dst);
        } else {
          basis.add(x[ver] ^ x[e.dst] ^ e.cost);
        }
      }
    }
  };
  dfs(dfs, -1, 0);
  while (q--) {
    int a, b;
    std::cin >> a >> b;
    std::bitset<D> ans(x[a] ^ x[b]);
    for (int i = 0; i < basis.rank(); ++i) {
      if (!ans[basis.msb[i]]) ans ^= basis.v[i];
    }
    std::cout << ans.to_ulong() << '\n';
  }
  return 0;
}

#line 1 "test/math/basis.test.cpp"
/*
 * @title 数学/基底
 *
 * verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2416
 */

#include <bitset>
#include <iostream>
#include <vector>

#line 1 "include/emthrm/graph/edge.hpp"
/**
 * @title 辺
 */

#ifndef EMTHRM_GRAPH_EDGE_HPP_
#define EMTHRM_GRAPH_EDGE_HPP_

#include <compare>

namespace emthrm {

template <typename CostType>
struct Edge {
  CostType cost;
  int src, dst;

  explicit Edge(const int src, const int dst, const CostType cost = 0)
      : cost(cost), src(src), dst(dst) {}

  auto operator<=>(const Edge& x) const = default;
};

}  // namespace emthrm

#endif  // EMTHRM_GRAPH_EDGE_HPP_
#line 1 "include/emthrm/math/basis.hpp"



#include <algorithm>
#line 6 "include/emthrm/math/basis.hpp"
#include <iterator>
#line 8 "include/emthrm/math/basis.hpp"

namespace emthrm {

template <int D>
struct Basis {
  std::vector<std::bitset<D>> v;
  std::vector<int> msb;

  Basis() = default;

  bool add(std::bitset<D> val) {
    const int n = rank();
    if (n == D) return false;
    for (int i = 0; i < n; ++i) {
      if (val[msb[i]]) val ^= v[i];
    }
    if (val.none()) return false;
    int m = D - 1;
    while (!val[m]) --m;
    if (v.empty()) [[unlikely]] {
      v.emplace_back(val);
      msb.emplace_back(m);
      return true;
    }
    const int idx = std::distance(std::upper_bound(msb.rbegin(), msb.rend(), m),
                                  msb.rend());
    v.emplace(std::next(v.begin(), idx), val);
    msb.emplace(std::next(msb.begin(), idx), m);
    for (int i = idx + 1; i <= n; ++i) {
      if (v[idx][msb[i]]) v[idx] ^= v[i];
    }
    for (int i = idx - 1; i >= 0; --i) {
      if (v[i][m]) v[i] ^= v[idx];
    }
    return true;
  }

  int rank() const { return v.size(); }

  inline bool operator<(const Basis& x) const {
    const int n = v.size();
    if (n != x.rank()) return n < x.rank();
    if (n == D) return false;
    for (int i = 0; i < n; ++i) {
      if (msb[i] != x.msb[i]) return msb[i] < x.msb[i];
    }
    for (int i = 0; i < n; ++i) {
      for (int j = msb[i] - 1; ; --j) {
        if (v[i][j] != x.v[i][j]) return x.v[i][j];
      }
    }
    return false;
  }
};

}  // namespace emthrm


#line 13 "test/math/basis.test.cpp"

int main() {
  constexpr int D = 60;
  int n, m, q;
  std::cin >> n >> m >> q;
  std::vector<std::vector<emthrm::Edge<long long>>> graph(n);
  while (m--) {
    int f, t;
    long long p;
    std::cin >> f >> t >> p;
    graph[f].emplace_back(f, t, p);
    graph[t].emplace_back(t, f, p);
  }
  std::vector<long long> x(n, -1);
  x[0] = 0;
  emthrm::Basis<D> basis;
  const auto dfs = [&graph, &x, &basis](auto dfs, const int par, const int ver)
      -> void {
    for (const emthrm::Edge<long long>& e : graph[ver]) {
      if (e.dst != par) {
        if (x[e.dst] == -1) {
          x[e.dst] = x[ver] ^ e.cost;
          dfs(dfs, ver, e.dst);
        } else {
          basis.add(x[ver] ^ x[e.dst] ^ e.cost);
        }
      }
    }
  };
  dfs(dfs, -1, 0);
  while (q--) {
    int a, b;
    std::cin >> a >> b;
    std::bitset<D> ans(x[a] ^ x[b]);
    for (int i = 0; i < basis.rank(); ++i) {
      if (!ans[basis.msb[i]]) ans ^= basis.v[i];
    }
    std::cout << ans.to_ulong() << '\n';
  }
  return 0;
}

Back to top page