AtCoderテンプレート

atcoder.cpp

// #define ONLINE_JUDGE
#ifdef ONLINE_JUDGE

#include <atcoder/all>
#include <bits/stdc++.h>
#include <boost/range/numeric.hpp>
#include <boost/range/algorithm.hpp>
#include <boost/algorithm/string/replace.hpp>
#include <boost/algorithm/string/join.hpp>
#include <boost/algorithm/string/classification.hpp>
#include <boost/algorithm/string/split.hpp>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/integer.hpp>
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#else

#define _GLIBCXX_DEBUG
#include <atcoder_template.h>

#endif

using namespace std;
using namespace atcoder;
// Boost
// cpp_int, powm, join, replace_all, split(dst, src, is_any_of());
// using namespace boost;
using namespace boost::algorithm;
using namespace boost::multiprecision;

// using ll = long long;
using ll = int64_t;
using pll = pair<ll, ll>;
template <typename T> using vec = vector<T>;
template <typename T> using vvec = vector<vector<T>>;

#define int ll

/*
#define REP(i, n) for (ll i = 0; i < (ll)(n); i++)
#define FOR(var, a, b) for (auto var = (a); var < (b); var++)
#define OVERLOAD_REP(_1, _2, TARGET, ...) TARGET
#define rep(...) OVERLOAD_REP(__VA_ARGS__, REP, FOR)(__VA_ARGS__)
#define RREP(i, n) for (ll i = (ll)(n - 1); i >= 0; i--)
#define RFOR(var, a, b) for (auto var = (b) - 1; var >= (a); var--)
#define rrep(...) OVERLOAD_REP(__VA_ARGS__, RREP, RFOR)(__VA_ARGS__)
*/
#define rep(i, n) for (ll i = 0, i##_len = n; i < i##_len; i++)

// #define foreach(elem, vec) for (auto&& (elem) : (vec))
#define MAX_NUM(type) numeric_limits<type>::max()
#define MIN_NUM(type) numeric_limits<type>::min()
#define all(arr) begin(arr), end(arr)
#define in(N) ll N; cin >> N
#define rin(N, A) vec<ll> A(N); rep(i, N) cin >> A[i]
#define bit(n) (1LL<<(n))

#define yes cout << "Yes" << endl
#define no cout << "No" << endl

// 繰り返し2乗法
// modを使う場合ACLの`pow_mod`を利用
ll pow(ll x, int p) {
  ll ans = 1;
  while(p > 0) {
    if(p & 1) {
      ans *= x;
    }
    x *= x;
    p >>= 1;
  }
  return ans;
}

ll sum(vec<ll> v) {
  return boost::accumulate(v, 0LL);
}

// 多次元vectorを作成
// `make_vec<int>({2,2,2}, 1)`で2x2x2、初期値1の配列となる
template<class T, size_t n, size_t idx = 0>
auto make_vec(const size_t (&d)[n], const T& init) noexcept {
    if constexpr (idx < n) return std::vector(d[idx], make_vec<T, n, idx + 1>(d, init));
    else return init;
}

// 多次元vectorを作成
// `make_vec<int>({2,2,2})`で2x2x2の配列となる
template<class T, size_t n>
auto make_vec(const size_t (&d)[n]) noexcept {
    return make_vec(d, T{});
}

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

#define pb push_back
#define mp make_pair
#define F first
#define S second

bool is_increasing(int x, int y, int z) {
  return x <= y && y <= z;
}

bool is_contained(int H, int W, int x, int y) {
  return is_increasing(0, x, H) && is_increasing(0, y, W);
}

// ---------------
// ----- TOC -----
template <typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &p);
template <typename T1, typename T2> istream &operator>>(istream &is, pair<T1, T2> &p);
template <typename T> ostream &operator<<(ostream &os, const vector<T> &v);
template <typename T> ostream &operator<<(ostream &os, const vector<vector<T>> &v);
template <typename T> ostream &operator<<(ostream &os, const vector<vector<vector<T>>> &v);
template <typename T> istream &operator>>(istream &is, vector<T> &v);
template <typename T, typename S> ostream &operator<<(ostream &os, const map<T, S> &mp);
template <typename T> ostream &operator<<(ostream &os, const set<T> &st);
template <typename T> ostream &operator<<(ostream &os, const multiset<T> &st);
template <typename T> ostream &operator<<(ostream &os, queue<T> q);
template <typename T> ostream &operator<<(ostream &os, deque<T> q);
template <typename T> ostream &operator<<(ostream &os, stack<T> st);
template <class T, class Container, class Compare> ostream &operator<<(ostream &os, priority_queue<T, Container, Compare> pq);
// --- END TOC ---
// ---------------

template <typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
  os << "(" << p.first << "," << p.second << ")";
  return os;
}

template <typename T1, typename T2> istream &operator>>(istream &is, pair<T1, T2> &p) {
  is >> p.first >> p.second;
  return is;
}

template <typename T> ostream &operator<<(ostream &os, const vector<T> &v) {
  os << "[";
  for (int i = 0; i < (int)v.size(); i++) {
    os << v[i] << (i + 1 != (int)v.size() ? ", " : "]");
  }
  return os;
}

template <typename T> ostream &operator<<(ostream &os, const vector<vector<T>> &v) {
  for (int i = 0; i < (int)v.size(); i++) {
    os << v[i] << endl;
  }
  return os;
}

template <typename T> ostream &operator<<(ostream &os, const vector<vector<vector<T>>> &v) {
  for (int i = 0; i < (int)v.size(); i++) {
    os << "i = " << i << endl;
    os << v[i];
  }
  return os;
}

template <typename T> istream &operator>>(istream &is, vector<T> &v) {
  for (T &in : v)
    is >> in;
  return is;
}

template <typename T, typename S> ostream &operator<<(ostream &os, const map<T, S> &mp) {
  for (auto &[key, val] : mp) {
    os << key << ":" << val << " ";
  }
  return os;
}

template <typename T> ostream &operator<<(ostream &os, const set<T> &st) {
  os << "{";
  auto itr = st.begin();
  for (int i = 0; i < (int)st.size(); i++) {
    os << *itr << (i + 1 != (int)st.size() ? ", " : "}");
    itr++;
  }
  return os;
}

template <typename T> ostream &operator<<(ostream &os, const multiset<T> &st) {
  auto itr = st.begin();
  for (int i = 0; i < (int)st.size(); i++) {
    os << *itr << (i + 1 != (int)st.size() ? " " : "");
    itr++;
  }
  return os;
}

template <typename T> ostream &operator<<(ostream &os, queue<T> q) {
  while (q.size()) {
    os << q.front() << " ";
    q.pop();
  }
  return os;
}

template <typename T> ostream &operator<<(ostream &os, deque<T> q) {
  while (q.size()) {
    os << q.front() << " ";
    q.pop_front();
  }
  return os;
}

template <typename T> ostream &operator<<(ostream &os, stack<T> st) {
  while (st.size()) {
    os << st.top() << " ";
    st.pop();
  }
  return os;
}

template <class T, class Container, class Compare> ostream &operator<<(ostream &os, priority_queue<T, Container, Compare> pq) {
  while (pq.size()) {
    os << pq.top() << " ";
    pq.pop();
  }
  return os;
}

using mint = modint998244353;
ostream &operator<<(ostream &os, const mint &i) {
  os << i.val();
  return os;
}

ostream &operator<<(ostream &os, const vector<mint> &v) {
  for (int i = 0; i < (int)v.size(); i++) {
    os << v[i].val() << (i + 1 != (int)v.size() ? " " : "");
  }
  return os;
}


#ifndef ONLINE_JUDGE

#define DEBUG_LOG

#endif

#ifdef DEBUG_LOG

#define line_debug() cout << "line: " << __LINE__ << endl;
#define coutd cout << "[debug] "
#define printd(x) cout << "[debug] " << #x << " = " << x << endl;

#else

ostream __coutd(nullptr);
#define line_debug() ;
#define coutd __coutd
#define printd(x) ;

#endif

// 降順
template <typename T> using p_queue = priority_queue<T>;
// 昇順
template <typename T> using rp_queue = priority_queue<T, vec<T>, greater<T>>;

class Point {
public:
  int x, y;
  Point() {}
  Point(int x, int y) : x(x), y(y) {}

  const Point operator+(const Point& rhs) const {
    return Point(x + rhs.x, y + rhs.y);
  }
  const Point operator-(const Point& rhs) const {
    return Point(x - rhs.x, y - rhs.y);
  }
};
ostream& operator<<(ostream& os, const Point &p) {
  os << p.x << p.y;
  return os;
}
istream& operator>>(istream &is, Point &p) {
  is >> p.x >> p.y;
  return is;
}



class UndirectedGraph {
 public:
  int N;
  vec<vec<int>> adj;
  UndirectedGraph(int N): N(N), adj(N) {};
  void merge(int a, int b) {
    adj[a].emplace_back(b);
    adj[b].emplace_back(a);
  }
};

vec<int> BFS(UndirectedGraph *G, int start) {
  class Node {
   public:
    int index;
    int way = -1;
    Node() {}
    Node(int index) : index(index) {}
    Node(int index, int way) : index(index), way(way) {}
  };
  queue<Node> q;
  vec<int> way(G->N, -1);
  q.emplace(Node(start, 0));
  way[start] = 0;
  while (q.size()) {
    Node now = q.front();
    q.pop();
    for (int next : G->adj[now.index]) {
      if (way[next] >= 0) continue;
      way[next] = now.way + 1;
      q.emplace(Node(next, now.way + 1));
    }
  }
  return way;
}


signed main() {
  // --- template
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  cout << std::fixed << std::setprecision(15);
  // ------


}