結果
| 問題 |
No.3016 ハチマキおじさん
|
| ユーザー |
 rrrriki
|
| 提出日時 | 2025-05-24 01:57:06 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 106 ms / 2,000 ms |
| コード長 | 50,206 bytes |
| コンパイル時間 | 3,960 ms |
| コンパイル使用メモリ | 343,540 KB |
| 実行使用メモリ | 11,008 KB |
| 最終ジャッジ日時 | 2025-05-24 01:57:14 |
| 合計ジャッジ時間 | 6,654 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 31 |
ソースコード
/**
* author: rrrriki
* created: 24.05.2025 01:48:04
*/
//#define USE_ACL
//#define USE_BOOST
#if !__INCLUDE_LEVEL__
#include <bits/stdc++.h>
#include __FILE__
signed main() {
cin.tie(0);
ios_base::sync_with_stdio(false);
ll N;
cin >> N;
vector<ll> A(N), B(N - 1);
for (int i = 0; i < N; i++) {
cin >> A[i];
}
for (int i = 0; i < N - 1; i++) {
cin >> B[i];
}
sort(ALL(A));
sort(ALL(B));
ll ans = 0;
ll cur = 0;
set<int> st;
st.emplace(A[N - 1]);
for (int i = 0; i < N - 1; i++) {
ans += abs(A[i] - B[i]);
}
cur = ans;
for (int i = N - 2; i >= 0; i--) {
cur -= abs(A[i] - B[i]);
cur += abs(A[i + 1] - B[i]);
if (cur < ans) {
ans = cur;
set<int> nst;
swap(st, nst);
st.emplace(A[i]);
} else if (cur == ans) {
st.emplace(A[i]);
}
}
cout << st.size() << "\n";
out_c(st);
return 0;
}
#else
// clang-format off
#ifdef USE_ACL
#include <atcoder/all>
using namespace atcoder;
using mint = modint998244353;
//using mint = modint1000000007;
#endif
#ifdef USE_BOOST
#include <boost/algorithm/string/classification.hpp>
#include <boost/algorithm/string/compare.hpp>
#include <boost/algorithm/string/join.hpp>
#include <boost/algorithm/string/replace.hpp>
#include <boost/algorithm/string/split.hpp>
#include <boost/algorithm/string/trim.hpp>
#include <boost/dynamic_bitset.hpp>
#include <boost/integer/extended_euclidean.hpp>
#include <boost/math/tools/minima.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/multiprecision/cpp_int.hpp>
using namespace boost::multiprecision;
#endif
#define ALL(x) x.begin(), x.end()
#define YES cout << "Yes\n"
#define NO cout << "No\n"
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define dbg(...) 42
#endif
using ll = long long;
using ld = long double;
#define INF (ll)1e18
using vl = vector<ll>;
using vll = vector<vector<ll>>;
/// コンテナの全出力 @tparam T コンテナの型 @param A コンテナ @param gap 区切り文字
template <class T> inline void out_c(T &A, string gap=" ") {auto itr = A.begin(); if (itr != A.end()) {cout << *itr; itr++;} while (itr != A.end()) {cout << gap << *itr; itr++;}cout << "\n"; return;}
template <class T> inline void out_c_pairs(T &A, string gap_inside=" ", string gap_outside = " ") {auto itr = A.begin();if (itr != A.end()) {cout << itr->first << gap_inside << itr->second;itr++;}while (itr != A.end()) {cout << gap_outside << itr->first << gap_inside << itr->second;itr++;}cout << "\n";return;}
/// べき乗を誤差なく計算する @param x 底 @param n 指数 @return x^n
inline ll _pow(ll x, ll n) {if (n == 0) return 1; ll val = _pow(x, n / 2); val *= val; if (n & 1) val *= x; return val;}
// マンハッタン距離
template <class T> inline T mnht(T a, T b, T c, T d) {return abs(a - c) + abs(b - d);}
/// ランレングス圧縮 @param s 圧縮する文字列 @return 圧縮した文字列を格納したvector<pair<char, int>>
inline vector<pair<char, int>> rle(const string &s){vector<pair<char, int>> vec;int cnt = 1; for(int i = 1; i < (int)s.size(); i++) {if(s[i] != s[i-1]){vec.emplace_back(s[i-1], cnt); cnt = 0;} cnt++;} vec.emplace_back(s.back(), cnt);return vec;}
/// ランレングス圧縮 @tparam T 圧縮するvectorの型 @param v 圧縮するvector @return 圧縮したvectorを格納したvector<pair<T, int>>
template <class T> inline vector<pair<T, int>> rle(const vector<T> &v) {vector<pair<T, int>> vec;int cnt = 1; for(int i = 1; i < (int)v.size(); i++) {if(v[i] != v[i-1]){vec.emplace_back(v[i-1], cnt); cnt = 0;} cnt++;} vec.emplace_back(v.back(), cnt);return vec;}
// 素数
inline bool is_prime(ll x){for (ll i=2; i*i<=x; i++){if(x%i==0)return false;}return true;}
inline map<ll,int> prime_factor(ll n) {map<ll,int> ret; for(ll i=2; i*i <= n; i++) {while(n%i == 0) {ret[i]++; n /= i;}} if(n != 1) ret[n]=1;return ret;}
inline vector<bool> sieve_of_era(ll n) {vector<bool> ret(n+1,true); ret[0]=false; ret[1]=false; for(ll i=2; i*i<=n; i++) {if(ret[i]) {for(ll j=i*2; j<=n; j+=i) {ret[j]=false;}}} return ret;}
// 約数全列挙
inline vector<ll> divisor(ll n) {vector<ll> ret; for(ll i=1; i*i <= n; i++) {if(n%i == 0) {ret.push_back(i); if(i*i != n) ret.emplace_back(n/i);}} sort(ALL(ret)); return ret;}
// 切り捨て、切り上げ、外側
inline constexpr ll ceil_div(const ll a, const ll b) {return (a + b - 1) / b - ((a + b - 1) % b < 0);}
inline constexpr ll floor_div(const ll a, const ll b) {return a / b - (a % b < 0);}
inline constexpr ll out_div(ll x, ll y) {ll d = x / y; return d * y == x ? d : ((x > 0) == (y > 0)) ? d + 1 : d - 1;}
// aよりもbが大きいならばaをbで更新する
template <typename T> bool chmax(T &a, const T& b) { if (a < b) { a = b; return true; } return false; }
// aよりもbが小さいならばaをbで更新する
template <typename T> bool chmin(T &a, const T& b) { if (a > b) { a = b; return true; } return false; }
/// 組み合わせの全探索 @param k 組み合わせの要素数
template <typename T>
bool next_combination(const T first, const T last, int k) {
const T subset = first + k;
// empty container | k = 0 | k == n
if (first == last || first == subset || last == subset) {
return false;
}
T src = subset;
while (first != src) {
src--;
if (*src < *(last - 1)) {
T dest = subset;
while (*src >= *dest) {
dest++;
}
iter_swap(src, dest);
rotate(src + 1, dest + 1, last);
rotate(subset, subset + (last - dest) - 1, last);
return true;
}
}
// restore
rotate(first, subset, last);
return false;
}
/**
* @brief PrimeUtil クラスは、ある上限までの数に対して素数判定や素因数分解、約数列挙を高速に行うためのクラスです。
*
* 使い方
*
* - PrimeUtil pu(n):= 1 から n までの最小素因数テーブルを構築
*
* - pu.is_prime(x):= x が素数かどうかを判定
*
* - pu.factor(x):= x の素因数分解結果を取得
*
* - pu.divisor(x):= x の約数を列挙
*
*/
class PrimeUtil {
private:
/// @brief spf[x] = x の最小素因数 (x >= 2)、x が素数の場合は spf[x] = x となる。
vector<int> spf;
/// @brief 数値の最大値
int maxN;
public:
/// @brief 1からnまでの最小素因数テーブル (spf) を構築 @param n 上限となる数 (1 <= n) @note 計算量はO(nloglogn)
PrimeUtil(int n) : spf(n + 1), maxN(n) {
// spf[i] を i で初期化 (i は素数かもしれないという仮定)
iota(spf.begin(), spf.end(), 0);
// エラトステネス類似の処理で spf を更新
for (int i = 2; i * i <= n; i++) {
if (spf[i] == i) { // i が素数のとき
for (int j = i * i; j <= n; j += i) {
// まだ更新されていない(=素数とされている)なら最小素因数を i に書き換える
if (spf[j] == j) {
spf[j] = (int)i;
}
}
}
}
}
/// @brief xが素数かどうかを判定 @param x 素数判定したい整数 @return xが素数ならtrue、そうでないならfalse @note 計算量はO(1)
bool is_prime(int x) const {
if (x < 2) return false;
assert(x <= maxN); // x が上限を超えていないか確認
return (spf[x] == x); // spf[x] == x なら素数
}
/// @brief xの素因数分解を行う @param x 素因数分解したい整数 @return xの素因数分解結果 (素因数 -> 指数) のmap @note 計算量はO(logx)
map<int, int> factor(int x) const {
map<int, int> ret;
if (x < 2) return ret; // x=1などは空
while (x > 1) { // SPF を使って高速に分解
int p = spf[x];
ret[p]++;
x /= p;
}
return ret;
}
/// @brief xの約数を列挙する @param x 約数を列挙したい整数 @param is_sorted 結果をソートするかどうか @return xの約数のvector @note 計算量はO(logx)
vector<int> divisor(int x, bool is_sorted = true) const {
// 素因数分解 O(logx)
auto mp = factor(x);
vector<int> ret;
ret.emplace_back(1);
// mpは (素数p -> 個数c) のmap
for (auto &kv : mp) {
int prime = kv.first;
int count = kv.second;
// 既存の約数に prime^1, prime^2, ... prime^count を掛けた新たな約数を追加
int nowSize = (int)ret.size();
long long base = 1;
for (int i = 0; i < count; i++) {
base *= prime;
for (int j = 0; j < nowSize; j++) {
ret.emplace_back(ret[j] * base);
}
}
}
if (is_sorted) sort(ret.begin(), ret.end());
return ret;
}
};
/// 二次元行列の回転 @tparam T 行列の要素の型 @param matrix 行列 @return 回転した行列
template <typename T>
inline vector<vector<T> > rotate_matrix(const vector<vector<T> > &matrix) {
int n = matrix.size();
int m = matrix[0].size();
vector<vector<T> > rotated(m, vector<T>(n));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
rotated[j][n - i - 1] = matrix[i][j];
}
}
return rotated;
}
/// string行列の回転 @param matrix 行列 @return 回転した行列
inline vector<string> rotate_matrix(const vector<string> &matrix) {
int n = matrix.size();
int m = matrix[0].size();
std::vector<string> rotated(m, string(n, ' '));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
rotated[j][n - i - 1] = matrix[i][j];
}
}
return rotated;
}
/// @brief Levenstein距離を計算する関数 @param s1 文字列1 @param s2 文字列2 @return Levenstein距離
int levenstein_distance(const string &s1, const string &s2) {
int n = s1.size();
int m = s2.size();
vector<vector<int> > dp(n + 1, vector<int>(m + 1, 0));
for (int i = 0; i <= n; i++) dp[i][0] = i;
for (int j = 0; j <= m; j++) dp[0][j] = j;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
dp[i][j] = min({dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + (s1[i - 1] != s2[j - 1])});
}
}
return dp[n][m];
}
// グラフ
/**
* @brief Edgeクラスはグラフのエッジ（辺）を表します。
*
* @tparam T エッジの重みの型（デフォルトはint）
*/
template <typename T = int>
struct Edge {
int from, to; // エッジの始点と終点
T cost; // エッジの重み
int idx; // エッジのインデックス（オプション）
// デフォルトコンストラクタ
Edge() = default;
// エッジをコストに基づいて比較するための演算子オーバーロード
bool operator<(const Edge &other) const { return cost < other.cost; }
bool operator>(const Edge &other) const { return cost > other.cost; }
friend std::ostream &operator<<(std::ostream &os, const Edge &edge) {
os << edge.to;
return os;
}
// コンストラクタ
Edge(int from, int to, T cost = 1, int idx = -1)
: from(from), to(to), cost(cost), idx(idx) {}
// エッジの終点をintとして取得するためのキャスト演算子
operator int() const { return to; }
};
/**
* @brief Graphクラスはグラフのデータ構造を表します。
* @tparam T エッジの重みの型（デフォルトはint）
*/
template <typename T = int>
struct Graph {
vector<vector<Edge<T> > > g; // 各ノードから出ているエッジのリスト
int es; // エッジの数
// デフォルトコンストラクタ
Graph() = default;
// ノード数nを指定するコンストラクタ
explicit Graph(int n) : g(n), es(0) {}
// グラフのサイズ（ノードの数）を返す
size_t size() const { return g.size(); }
// 有向エッジを追加する関数
void add_directed_edge(int from, int to, T cost = 1) {
g[from].emplace_back(from, to, cost, es++);
}
// 無向エッジを追加する関数
void add_edge(int from, int to, T cost = 1) {
g[from].emplace_back(from, to, cost, es);
g[to].emplace_back(to, from, cost, es++);
}
/// @brief エッジを読み込む関数 @param M エッジの数 @param padding インデックスのオフセット @param weighted 重み付きかどうか @param directed 有向かどうか
void read(int M, int padding = -1, bool weighted = false,
bool directed = false) {
for (int i = 0; i < M; i++) {
int a, b;
cin >> a >> b;
a += padding;
b += padding;
T c = T(1);
if (weighted) cin >> c;
if (directed)
add_directed_edge(a, b, c);
else
add_edge(a, b, c);
}
}
// 演算子オーバーロード：インデックスによるエッジのリストへのアクセス
inline vector<Edge<T> > &operator[](const int &k) { return g[k]; }
// 演算子オーバーロード（const版）：インデックスによるエッジのリストへのアクセス
inline const vector<Edge<T> > &operator[](const int &k) const { return g[k]; }
};
/// @brief エッジのリスト @tparam T エッジの重みの型
template <typename T = int>
using Edges = vector<Edge<T> >;
// ダイクストラ法
/**
* @brief dijkstra関数はダイクストラ法を用いて最短経路を求める関数です。
* @tparam T エッジの重みの型
* @param g グラフ
* @param s 始点
* @return vector<T> 始点から各頂点への最短経路の長さ
* @note 計算量はO((E+V)logV)
*/
template <typename T>
vector<T> dijkstra(Graph<T> &g, int s) {
vector<T> dist(g.size(), numeric_limits<T>::max());
dist[s] = 0;
priority_queue<pair<T, int>, vector<pair<T, int> >, greater<pair<T, int> > > pq;
pq.emplace(0, s);
while (!pq.empty()) {
auto [d, v] = pq.top();
pq.pop();
if (dist[v] < d) continue;
for (auto e : g[v]) {
if (dist[e.to] > dist[v] + e.cost) {
dist[e.to] = dist[v] + e.cost;
pq.emplace(dist[e.to], e.to);
}
}
}
return dist;
}
#ifndef USE_ACL
struct dsu {
public:
dsu() : _n(0) {}
explicit dsu(int n) : _n(n), parent_or_size(n, -1) {}
int merge(int a, int b) {
assert(0 <= a && a < _n);
assert(0 <= b && b < _n);
int x = leader(a), y = leader(b);
if (x == y) return x;
if (-parent_or_size[x] < -parent_or_size[y]) std::swap(x, y);
parent_or_size[x] += parent_or_size[y];
parent_or_size[y] = x;
return x;
}
bool same(int a, int b) {
assert(0 <= a && a < _n);
assert(0 <= b && b < _n);
return leader(a) == leader(b);
}
int leader(int a) {
assert(0 <= a && a < _n);
if (parent_or_size[a] < 0) return a;
return parent_or_size[a] = leader(parent_or_size[a]);
}
int size(int a) {
assert(0 <= a && a < _n);
return -parent_or_size[leader(a)];
}
std::vector<std::vector<int> > groups() {
std::vector<int> leader_buf(_n), group_size(_n);
for (int i = 0; i < _n; i++) {
leader_buf[i] = leader(i);
group_size[leader_buf[i]]++;
}
std::vector<std::vector<int> > result(_n);
for (int i = 0; i < _n; i++) {
result[i].reserve(group_size[i]);
}
for (int i = 0; i < _n; i++) {
result[leader_buf[i]].push_back(i);
}
result.erase(
std::remove_if(result.begin(), result.end(),
[&](const std::vector<int> &v) { return v.empty(); }),
result.end());
return result;
}
private:
int _n;
// root node: -1 * component size
// otherwise: parent
std::vector<int> parent_or_size;
};
#endif
/**
* @brief 重み付きUnionFind @tparam T 重みの型
*
* 使い方
*
* - UnionFindWithPotential<T> uf(n):= n要素のUnionFindWithPotentialを宣言
*
* - uf.merge(x, y, p):= P(x) = P(y) + p でマージ
*
* - uf.diff(x, y):= P(x) - P(y) を求める
*
* - uf.same(x, y):= xとyが同じ連結成分に属するかどうか
*
* - uf.potential(x):= xのポテンシャルを求める P(x) - P(root(x))
*
* - uf.size(x):= xが属する連結成分のサイズを求める
*
* - uf.root(x):= xの根を求める
*
*/
template <class T>
struct UnionFindWithPotential {
vector<int> dat; // 親の番号 根の場合は-1
vector<T> pot; // 親との差分
UnionFindWithPotential(int N) : dat(N, -1), pot(N, T()) {}
/// @brief xの根を求める @return 根
int root(int x) {
if (dat[x] < 0) return x;
int r = root(dat[x]);
pot[x] += pot[dat[x]];
return dat[x] = r;
}
/// @brief xのポテンシャルを求める @return P(x) - P(root(x))
T potential(int x) {
root(x);
return pot[x];
}
bool same(int x, int y) { return root(x) == root(y); }
/// @brief xとyのポテンシャルの差を求める @return P(x) - P(y)
T diff(int x, int y) { return potential(x) - potential(y); }
/// @brief P(x) = P(y) + p でマージ @param p ポテンシャルの差 @return マージできたかどうか
bool merge(int x, int y, T p) {
p += potential(y) - potential(x);
x = root(x), y = root(y);
if (x == y) return p == T();
if (dat[x] < dat[y]) swap(x, y), p = -p;
dat[y] += dat[x];
dat[x] = y;
pot[x] = p;
return true;
}
/// @brief xが属する連結成分のサイズを求める @return xが属する連結成分のサイズ
int size(int x) { return -dat[root(x)]; }
};
/**
* @brief krsukal関数はクラスカル法を用いて最小/最大全域木を求める関数です。
* @tparam T エッジの重みの型
* @param g グラフ
* @param s 最小全域木を求める場合は"min"、最大全域木を求める場合は"max"を指定
* @return T 最小/最大全域木の重み
* @note 計算量はO(ElogV)
*/
template <typename T>
T kruskal(Graph<T> &g, string s = "min") {
T res = 0;
int n = g.size();
dsu dsu(n);
Edges<T> edges;
for (int i = 0; i < n; i++) {
for (auto e : g[i]) {
edges.emplace_back(e);
}
}
if (s == "max")
sort(ALL(edges), greater<Edge<T> >());
else
sort(ALL(edges));
for (auto e : edges) {
if (dsu.same(e.from, e.to)) continue;
dsu.merge(e.from, e.to);
res += e.cost;
}
return res;
}
/**
* @brief GRID構造体はグリッドを扱うための構造体です
* @tparam T グリッドの要素の型 (デフォルトはchar)
*
* 使い方
*
* - GRID<T> grid:= グリッドを宣言
*
* - GRID<T> grid(H, W, default_value):= H x W のグリッドを宣言
*
* - grid.wall('#'):= 通れないマスを指定
*
* - grid.read(h, w, default_wall):= h x w のグリッドを読み込む
*
* - grid.bfs(si, sj):= (si, sj) から各マスへの最短距離を求める
*
* - grid.bfs_vis(si, sj):= BFSを1つの始点から開始し、到達可能領域を探索
*
* - grid[i][j]:= (i, j) の要素にアクセス
*
* - grid.print(gap):= グリッドの出力
*
* - grid.get_positions('.'): '.'の座標を取得
*
* - grid.get_start_goal('S', 'G'): スタートとゴールの座標を取得
*/
template <typename T = char>
struct GRID {
vector<vector<T> > field; // グリッドデータ
unordered_set<T> wall_set; // 通れないマスの集合
vector<vector<bool> > vis; // 到達確認用
const vector<pair<int, int> > directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int H, W; // 高さと幅
/// @brief デフォルトコンストラクタ
GRID() = default;
/// @brief コンストラクタ @param h 高さ @param w 幅
GRID(int h, int w, T default_value = '.') : H(h), W(w) {
field.assign(H, vector<T>(W, default_value));
vis.assign(H, vector<bool>(W, false));
}
/// @brief 通れないマスを追加 @param wall_obj 通れないマス
void wall(T wall_obj) {
wall_set.emplace(wall_obj);
}
/// @brief グリッドの読み込み @param h 高さ @param w 幅 @param default_wall 通れないマスのデフォルト値
void read(int h, int w, T default_wall = '#') {
H = h;
W = w;
field.resize(H, vector<T>(W));
vis.assign(H, vector<bool>(W, false)); // visを初期化
wall_set.emplace(default_wall);
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
cin >> field[i][j];
}
}
}
/// @brief (si, sj) から各マスへの最短距離を求める @param si 始点の行 @param sj 始点の列 @return (si, sj) から各マスへの最短距離
vector<vector<ll> > bfs(int si, int sj) const {
vector<vector<ll> > dist(H, vector<ll>(W, INF));
queue<pair<int, int> > q;
dist[si][sj] = 0;
q.push({si, sj});
// BFS処理
while (!q.empty()) {
auto [i, j] = q.front();
q.pop();
for (const auto &[di, dj] : directions) {
int ni = i + di, nj = j + dj;
if (ni < 0 || ni >= H || nj < 0 || nj >= W) continue; // 範囲外
if (wall_set.count(field[ni][nj])) continue; // 通れないマス
if (dist[ni][nj] != INF) continue; // 既に訪問済み
dist[ni][nj] = dist[i][j] + 1;
q.push({ni, nj});
}
}
return dist;
}
/// @brief BFSを1つの始点から開始し、到達可能領域を探索 @param si 始点の行 @param sj 始点の列
void bfs_vis(int si, int sj) {
if (si < 0 || si >= H || sj < 0 || sj >= W || wall_set.count(field[si][sj]) || vis[si][sj]) {
return; // 無効な始点なら探索しない
}
queue<pair<int, int> > q;
vis[si][sj] = true;
q.push({si, sj});
// BFS処理
while (!q.empty()) {
auto [i, j] = q.front();
q.pop();
for (const auto &[di, dj] : directions) {
int ni = i + di, nj = j + dj;
if (ni < 0 || ni >= H || nj < 0 || nj >= W) continue; // 範囲外
if (wall_set.count(field[ni][nj]) || vis[ni][nj]) continue; // 壁または訪問済み
vis[ni][nj] = true;
q.push({ni, nj});
}
}
}
/// @brief (i, j) の要素にアクセス @param i 行 @param j 列 @return (i, j) の要素
vector<T> &operator[](int i) {
return field[i];
}
const vector<T> &operator[](int i) const {
return field[i];
}
/// @brief グリッドの出力 @param gap 区切り文字
void print(string gap = "") {
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
cout << field[i][j];
if (j < W - 1) cout << gap;
}
cout << "\n";
}
}
/// @brief 座標の取得 @param obj オブジェクト @return オブジェクトの座標
vector<pair<int, int> > get_positions(T obj = '.') {
vector<pair<int, int> > positions;
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
if (field[i][j] == obj) {
positions.emplace_back(i, j);
}
}
}
return positions;
}
/// @brief スタートとゴールの座標を取得 @param start スタートのオブジェクト @param goal ゴールのオブジェクト @return スタートとゴールの座標
pair<pair<int, int>, pair<int, int> > get_start_goal(T start = 'S', T goal = 'G') {
pair<int, int> s, g;
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
if (field[i][j] == start) {
s = {i, j};
}
if (field[i][j] == goal) {
g = {i, j};
}
}
}
return {s, g};
}
};
/**
* @brief CumulativeSum2Dは二次元累積和を計算するための構造体です。
* @tparam T 累積和の型
*
* 使い方
*
* - CumulativeSum2D<T> cumsum(W, H):= W x H の二次元累積和を宣言
*
* - add(x, y, z):= x, y に z を加算
*
* - build():= 二次元累積和を構築
*
* - query(sx, sy, gx, gy):= (sx, sy) から (gx, gy) までの和を計算 [sx, gx), [sy, gy)
*/
template <class T>
struct CumulativeSum2D {
vector<vector<T> > data;
/// @brief W x H の二次元累積和を宣言 @param W 幅 @param H 高さ
CumulativeSum2D(int W, int H) : data(W + 1, vector<T>(H + 1, 0)) {}
/// @brief x, y に z を加算 @param x x座標 @param y y座標 @param z 加算する値
void add(int x, int y, T z) {
++x, ++y;
if (x >= (int)data.size() || y >= (int)data[0].size()) return;
data[x][y] += z;
}
/// @brief 二次元累積和を構築
void build() {
for (int i = 1; i < (int)data.size(); i++) {
for (int j = 1; j < (int)data[i].size(); j++) {
data[i][j] += data[i][j - 1] + data[i - 1][j] - data[i - 1][j - 1];
}
}
}
/// @brief (sx, sy) から (gx, gy) までの和を計算 [sx, gx), [sy, gy)
/// @param sx x座標の始点 @param sy y座標の始点 @param gx x座標の終点 @param gy y座標の終点 @note gxとgyは含まれない
T query(int sx, int sy, int gx, int gy) const {
return (data[gx][gy] - data[sx][gy] - data[gx][sy] + data[sx][sy]);
}
};
/**
* @brief 座標圧縮を扱う汎用構造体
* @tparam T 座標の型
*
* 使い方
*
* - build(vector<T>&... vectors):=座標圧縮を行い圧縮後の座標をtupleで返す
*
* - build(vector<vector<T>>& vectors):=二次元vector版
*
* - compress(T value):=座標を圧縮する
*
* - decompress(int idx):=圧縮された座標を元に戻す
*
* - compress_vector(vector<T>& vec):=vectorを圧縮する
*
* - decompress_vector(vector<int>& vec):=圧縮されたvectorを元に戻す
*/
template <typename T>
struct CoordCompressor {
unordered_map<T, int> compressed_map; // 元の座標 -> 圧縮後の座標
unordered_map<int, T> reverse_compressed_map; // 圧縮後の座標 -> 元の座標
/// @brief 座標圧縮を行う (可変長引数の対応) @param vectors 複数のvectorを受け取り圧縮
template <typename... Vectors>
auto build(Vectors &...vectors) {
// 座標のsetを作成
set<T> coords;
(coords.insert(vectors.begin(), vectors.end()), ...);
// 座標圧縮用のmapを作成
int idx = 0;
for (const auto &coord : coords) {
compressed_map[coord] = idx;
reverse_compressed_map[idx] = coord;
++idx;
}
// 各vectorを圧縮、圧縮されたvectorのtupleを返す
return make_tuple(compress_vector(vectors)...);
}
/// @brief vector<vector<T>> の圧縮 (二次元vector対応)
vector<vector<int> > build(const vector<vector<T> > &vectors) {
// 座標のsetを作成
set<T> coords;
for (const auto &vec : vectors) {
coords.insert(vec.begin(), vec.end());
}
// 座標圧縮用のmapを作成
int idx = 0;
for (const auto &coord : coords) {
compressed_map[coord] = idx;
reverse_compressed_map[idx] = coord;
++idx;
}
// 二次元vectorを圧縮
vector<vector<int> > compressedVectors(vectors.size());
for (size_t i = 0; i < vectors.size(); ++i) {
compressedVectors[i] = compress_vector(vectors[i]);
}
// 圧縮された二次元vectorを返す
return compressedVectors;
}
/// @brief 値を圧縮する @param value 圧縮する値 @return 圧縮された値
int compress(const T &value) const {
assert(compressed_map.count(value));
return compressed_map.at(value);
}
/// @brief 圧縮値を元に戻す @param idx 圧縮されたインデックス @return 元の値
T decompress(int idx) const {
assert(reverse_compressed_map.count(idx));
return reverse_compressed_map.at(idx);
}
/// @brief vectorを圧縮する @param vec 圧縮するvector @return 圧縮されたvector
vector<int> compress_vector(const vector<T> &vec) const {
vector<int> compressedVec(vec.size());
transform(vec.begin(), vec.end(), compressedVec.begin(),
[&](const T &val) { return compress(val); });
return compressedVec;
}
/// @brief vectorを元に戻す @param vec 圧縮されたvector @return 元の値に戻されたvector
vector<T> decompress_vector(const vector<int> &vec) const {
vector<T> decompressedVec(vec.size());
transform(vec.begin(), vec.end(), decompressedVec.begin(),
[&](int val) { return decompress(val); });
return decompressedVec;
}
};
/**
* @brief Rolling-Hash(ローリングハッシュ)
*
* 使い方
*
* - RollingHash rh:= ローリングハッシュを宣言
*
* - build(s):= 文字列sのハッシュ値を計算
*
* - query(s, l, r):= 文字列sの[l, r)のハッシュ値を計算
*
* - combine(h1, h2, h2len):= ハッシュ値h1と長さh2lenのハッシュ値h2を結合する
*
* - lcp(a, l1, r1, b, l2, r2):= ハッシュテーブルaの区間[l1,r1)と、ハッシュテーブルbの区間[l2,r2)の最長共通接頭辞の長さを求める
*
* @see https://qiita.com/keymoon/items/11fac5627672a6d6a9f6
* @see https://ei1333.github.io/library/string/rolling-hash.hpp
*/
struct RollingHash {
static const uint64_t mod = (1ull << 61ull) - 1;
using uint128_t = __uint128_t;
const uint64_t base;
vector<uint64_t> power;
/// @brief 加算 @param a 加数 @param b 加数 @return 和
static inline uint64_t add(uint64_t a, uint64_t b) {
if ((a += b) >= mod) a -= mod;
return a;
}
/// @brief 乗算 @param a 乗数 @param b 乗数 @return 積
static inline uint64_t mul(uint64_t a, uint64_t b) {
uint128_t c = (uint128_t)a * b;
return add(c >> 61, c & mod);
}
/// @brief 2^61-1 未満の乱数を生成する
static inline uint64_t generate_base() {
mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<uint64_t> rand(1, RollingHash::mod - 1);
return rand(mt);
}
/// @brief ハッシュテーブルのサイズを拡張する @param sz 拡張するサイズ
inline void expand(size_t sz) {
if (power.size() < sz + 1) {
int pre_sz = (int)power.size();
power.resize(sz + 1);
for (int i = pre_sz - 1; i < (int)sz; i++) {
power[i + 1] = mul(power[i], base);
}
}
}
explicit RollingHash(uint64_t base = generate_base()) : base(base), power{1} {}
/// @brief 文字列sのハッシュ値を計算する @param s 文字列 @return ハッシュ値
vector<uint64_t> build(const string &s) const {
int sz = s.size();
vector<uint64_t> hashed(sz + 1);
for (int i = 0; i < sz; i++) {
hashed[i + 1] = add(mul(hashed[i], base), s[i]);
}
return hashed;
}
/// @brief ベクタsのハッシュ値を計算する @tparam T ベクタの型 @param s ベクタ @return ハッシュ値
template <typename T>
vector<uint64_t> build(const vector<T> &s) const {
int sz = s.size();
vector<uint64_t> hashed(sz + 1);
for (int i = 0; i < sz; i++) {
hashed[i + 1] = add(mul(hashed[i], base), s[i]);
}
return hashed;
}
/// @brief 文字列sの[l, r)のハッシュ値を計算する @param s 文字列 @param l 左端 @param r 右端 @return ハッシュ値
uint64_t query(const vector<uint64_t> &s, int l, int r) {
expand(r - l);
return add(s[r], mod - mul(s[l], power[r - l]));
}
/// @brief ハッシュ値h1とハッシュ値h2を結合する @param h1 ハッシュ値1 @param h2 ハッシュ値2 @param h2len ハッシュ値2の長さ @return 結合されたハッシュ値
uint64_t combine(uint64_t h1, uint64_t h2, size_t h2len) {
expand(h2len);
return add(mul(h1, power[h2len]), h2);
}
/// @brief ハッシュテーブルaの区間[l1,r1)と、ハッシュテーブルbの区間[l2,r2)の最長共通接頭辞の長さを求める @param a ハッシュテーブルa @param l1 左端 @param r1 右端 @param b ハッシュテーブルb @param l2 左端 @param r2 右端 @return 最長共通接頭辞の長さ
int lcp(const vector<uint64_t> &a, int l1, int r1, const vector<uint64_t> &b, int l2, int r2) {
int len = min(r1 - l1, r2 - l2);
int low = 0, high = len + 1;
while (high - low > 1) {
int mid = (low + high) / 2;
if (query(a, l1, l1 + mid) == query(b, l2, l2 + mid))
low = mid;
else
high = mid;
}
return low;
}
};
/**
* @brief K-Shortest-PathをYen’s Algorithm により求める関数
* @tparam T グラフの重みの型 @param g グラフ @param s 始点 @param t 終点 @param k 最短経路の数
*
* 使い方
*
* - k_shotest_path(g, s, t, k): 重み付き有向グラフ g の頂点 s から t へのパスのうち,
* 昇順 k 個のパスの長さとそのパスの辺番号の列を返す(パスの個数が k 個に満たないとき全てを返す)
*
* @return vector<pair<T, vector<int>>> 最短経路の長さと経路 @note 計算量はO(kV((E+V)logV))
*/
template <typename T>
vector<pair<T, vector<int> > > k_shortest_path(const Graph<T> &g, int s, int t, int k) {
assert(s != t);
int N = (int)g.size();
int M = 0;
for (int i = 0; i < N; i++) M += (int)g[i].size();
vector<int> latte(M), malta(M);
vector<T> cost(M);
for (int i = 0; i < N; i++) {
for (auto &e : g[i]) {
latte[e.idx] = i;
malta[e.idx] = e.to;
cost[e.idx] = e.cost;
}
}
const auto INF_ = numeric_limits<T>::max();
vector<int> dame(M, -1);
int timestamp = 0;
// dijkstra
auto shortest_path = [&](vector<T> &dist, vector<int> &from, vector<int> &id, int st) {
using Pi = pair<T, int>;
priority_queue<Pi, vector<Pi>, greater<> > que;
que.emplace(dist[st], st);
while (!que.empty()) {
T cost;
int idx;
tie(cost, idx) = que.top();
que.pop();
if (dist[idx] < cost) continue;
if (idx == t) return;
for (auto &e : g[idx]) {
auto next_cost = cost + e.cost;
if (dist[e.to] <= next_cost) continue;
if (dame[e.idx] == timestamp) continue;
dist[e.to] = next_cost;
from[e.to] = idx;
id[e.to] = e.idx;
que.emplace(dist[e.to], e.to);
}
}
};
auto restore = [](const vector<int> &es, const vector<int> &vs, int from,
int to) {
vector<int> tap;
while (to != from) {
tap.emplace_back(es[to]);
to = vs[to];
}
reverse(begin(tap), end(tap));
return tap;
};
vector<T> dist(g.size(), INF_);
vector<int> from(g.size(), -1), id(g.size(), -1);
dist[s] = 0;
shortest_path(dist, from, id, s);
if (dist[t] == INF_) return {};
vector<pair<T, vector<int> > > A;
set<pair<T, vector<int> > > B;
A.emplace_back(dist[t], restore(id, from, s, t));
for (int i = 1; i < k; i++) {
dist.assign(g.size(), INF_);
from.assign(g.size(), -1);
id.assign(g.size(), -1);
dist[s] = 0;
vector<int> candidate(A.size());
iota(begin(candidate), end(candidate), 0);
auto &last_path = A.back().second;
int cur = s;
for (int j = 0; j < last_path.size(); j++) {
for (auto &k : candidate) {
if (j < A[k].second.size()) dame[A[k].second[j]] = timestamp;
}
vector<T> dist2{dist};
vector<int> from2{from}, id2{id};
shortest_path(dist2, from2, id2, cur);
++timestamp;
if (dist2[t] != INF_) {
auto path = restore(id2, from2, s, t);
bool ok = true;
for (auto &p : candidate) {
if (path == A[p].second) {
ok = false;
break;
}
}
if (ok) B.emplace(dist2[t], path);
}
vector<int> accept;
for (auto &k : candidate) {
if (j < A[k].second.size() && A[k].second[j] == last_path[j]) {
accept.emplace_back(k);
}
}
dist[malta[last_path[j]]] =
dist[latte[last_path[j]]] + cost[last_path[j]];
from[malta[last_path[j]]] = latte[last_path[j]];
id[malta[last_path[j]]] = last_path[j];
cur = malta[last_path[j]];
candidate = move(accept);
}
if (B.size()) {
A.emplace_back(*B.begin());
B.erase(B.begin());
}
}
return A;
}
// ---------------------------------------
// ----- segment trees by @rrrrikiOW -----
// ---------------------------------------
// ----- Based on AtCoder Library --------
// -------------- VER.1.1.0 --------------
// ----- Last Update: 2024/03/03 ---------
// ---------------------------------------
/// @brief 2の冪に切り上げる @param n 数 @return 2の冪
inline int ceil_pow2(int n) {
int x = 0;
while ((1U << x) < (unsigned int)(n)) x++;
return x;
}
#ifndef USE_ACL
/// @brief セグメント木
/// @tparam S セグメント木の型 @tparam op セグメント木の演算 @tparam e セグメント木の単位元
template <class S, S (*op)(S, S), S (*e)()>
struct segtree {
public:
segtree() : segtree(0) {}
explicit segtree(int n) : segtree(std::vector<S>(n, e())) {}
explicit segtree(const std::vector<S> &v) : _n(int(v.size())) {
log = ceil_pow2(_n);
size = 1 << log;
d = std::vector<S>(2 * size, e());
for (int i = 0; i < _n; i++) d[size + i] = v[i];
for (int i = size - 1; i >= 1; i--) {
update(i);
}
}
/// @brief 0-indexed で k 番目の要素を x に変更する O(logN)
void set(int p, S x) {
assert(0 <= p && p < _n);
p += size;
d[p] = x;
for (int i = 1; i <= log; i++) update(p >> i);
}
/// @brief 0-indexed で k 番目の要素を取得する O(logN)
S get(int p) const {
assert(0 <= p && p < _n);
return d[p + size];
}
/// @brief op(a[l], ..., a[r - 1]) を、モノイドの性質を満たしていると仮定して計算します。 l=r のときは e() を返します。 O(logN)
S prod(int l, int r) const {
assert(0 <= l && l <= r && r <= _n);
S sml = e(), smr = e();
l += size;
r += size;
while (l < r) {
if (l & 1) sml = op(sml, d[l++]);
if (r & 1) smr = op(d[--r], smr);
l >>= 1;
r >>= 1;
}
return op(sml, smr);
}
/// @brief op(a[0], ..., a[n - 1]) を、モノイドの性質を満たしていると仮定して計算します O(1)
S all_prod() const { return d[1]; }
template <bool (*f)(S)>
int max_right(int l) const {
return max_right(l, [](S x) { return f(x); });
}
template <class F>
int max_right(int l, F f) const {
assert(0 <= l && l <= _n);
assert(f(e()));
if (l == _n) return _n;
l += size;
S sm = e();
do {
while (l % 2 == 0) l >>= 1;
if (!f(op(sm, d[l]))) {
while (l < size) {
l = (2 * l);
if (f(op(sm, d[l]))) {
sm = op(sm, d[l]);
l++;
}
}
return l - size;
}
sm = op(sm, d[l]);
l++;
} while ((l & -l) != l);
return _n;
}
template <bool (*f)(S)>
int min_left(int r) const {
return min_left(r, [](S x) { return f(x); });
}
template <class F>
int min_left(int r, F f) const {
assert(0 <= r && r <= _n);
assert(f(e()));
if (r == 0) return 0;
r += size;
S sm = e();
do {
r--;
while (r > 1 && (r % 2)) r >>= 1;
if (!f(op(d[r], sm))) {
while (r < size) {
r = (2 * r + 1);
if (f(op(d[r], sm))) {
sm = op(d[r], sm);
r--;
}
}
return r + 1 - size;
}
sm = op(d[r], sm);
} while ((r & -r) != r);
return 0;
}
private:
int _n, size, log;
std::vector<S> d;
void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
};
/// @brief 遅延セグメント木
/// @tparam S セグメント木の型 @tparam op セグメント木の演算 @tparam e セグメント木の単位元
/// @tparam F 作用素の型 @tparam mapping 作用素の演算 @tparam composition 作用素の合成 @tparam id 作用素の単位元
template <class S,
S (*op)(S, S),
S (*e)(),
class F,
S (*mapping)(F, S),
F (*composition)(F, F),
F (*id)()>
struct lazy_segtree {
public:
lazy_segtree() : lazy_segtree(0) {}
explicit lazy_segtree(int n) : lazy_segtree(std::vector<S>(n, e())) {}
explicit lazy_segtree(const std::vector<S> &v) : _n(int(v.size())) {
log = ceil_pow2(_n);
size = 1 << log;
d = std::vector<S>(2 * size, e());
lz = std::vector<F>(size, id());
for (int i = 0; i < _n; i++) d[size + i] = v[i];
for (int i = size - 1; i >= 1; i--) {
update(i);
}
}
/// @brief 0-indexed で k 番目の要素を x に変更する O(logN)
void set(int p, S x) {
assert(0 <= p && p < _n);
p += size;
for (int i = log; i >= 1; i--) push(p >> i);
d[p] = x;
for (int i = 1; i <= log; i++) update(p >> i);
}
/// @brief 0-indexed で k 番目の要素を取得する O(logN)
S get(int p) {
assert(0 <= p && p < _n);
p += size;
for (int i = log; i >= 1; i--) push(p >> i);
return d[p];
}
/// @brief op(a[l], ..., a[r - 1]) を、モノイドの性質を満たしていると仮定して計算します。 l=r のときは e() を返します。 O(logN)
S prod(int l, int r) {
assert(0 <= l && l <= r && r <= _n);
if (l == r) return e();
l += size;
r += size;
for (int i = log; i >= 1; i--) {
if (((l >> i) << i) != l) push(l >> i);
if (((r >> i) << i) != r) push((r - 1) >> i);
}
S sml = e(), smr = e();
while (l < r) {
if (l & 1) sml = op(sml, d[l++]);
if (r & 1) smr = op(d[--r], smr);
l >>= 1;
r >>= 1;
}
return op(sml, smr);
}
/// @brief op(a[0], ..., a[n - 1]) を、モノイドの性質を満たしていると仮定して計算します O(1)
S all_prod() { return d[1]; }
/// @brief a[p] = f(a[p])
void apply(int p, F f) {
assert(0 <= p && p < _n);
p += size;
for (int i = log; i >= 1; i--) push(p >> i);
d[p] = mapping(f, d[p]);
for (int i = 1; i <= log; i++) update(p >> i);
}
/// @brief [l, r) の要素に f を作用させます O(logN)
void apply(int l, int r, F f) {
assert(0 <= l && l <= r && r <= _n);
if (l == r) return;
l += size;
r += size;
for (int i = log; i >= 1; i--) {
if (((l >> i) << i) != l) push(l >> i);
if (((r >> i) << i) != r) push((r - 1) >> i);
}
{
int l2 = l, r2 = r;
while (l < r) {
if (l & 1) all_apply(l++, f);
if (r & 1) all_apply(--r, f);
l >>= 1;
r >>= 1;
}
l = l2;
r = r2;
}
for (int i = 1; i <= log; i++) {
if (((l >> i) << i) != l) update(l >> i);
if (((r >> i) << i) != r) update((r - 1) >> i);
}
}
template <bool (*g)(S)>
int max_right(int l) {
return max_right(l, [](S x) { return g(x); });
}
template <class G>
int max_right(int l, G g) {
assert(0 <= l && l <= _n);
assert(g(e()));
if (l == _n) return _n;
l += size;
for (int i = log; i >= 1; i--) push(l >> i);
S sm = e();
do {
while (l % 2 == 0) l >>= 1;
if (!g(op(sm, d[l]))) {
while (l < size) {
push(l);
l = (2 * l);
if (g(op(sm, d[l]))) {
sm = op(sm, d[l]);
l++;
}
}
return l - size;
}
sm = op(sm, d[l]);
l++;
} while ((l & -l) != l);
return _n;
}
template <bool (*g)(S)>
int min_left(int r) {
return min_left(r, [](S x) { return g(x); });
}
template <class G>
int min_left(int r, G g) {
assert(0 <= r && r <= _n);
assert(g(e()));
if (r == 0) return 0;
r += size;
for (int i = log; i >= 1; i--) push((r - 1) >> i);
S sm = e();
do {
r--;
while (r > 1 && (r % 2)) r >>= 1;
if (!g(op(d[r], sm))) {
while (r < size) {
push(r);
r = (2 * r + 1);
if (g(op(d[r], sm))) {
sm = op(d[r], sm);
r--;
}
}
return r + 1 - size;
}
sm = op(d[r], sm);
} while ((r & -r) != r);
return 0;
}
private:
int _n, size, log;
std::vector<S> d;
std::vector<F> lz;
void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
void all_apply(int k, F f) {
d[k] = mapping(f, d[k]);
if (k < size) lz[k] = composition(f, lz[k]);
}
void push(int k) {
all_apply(2 * k, lz[k]);
all_apply(2 * k + 1, lz[k]);
lz[k] = id();
}
};
#endif
/// @brief 双対セグメント木 @tparam T セグメント木の型 @tparam composition セグメント木のマージ関数 @tparam id セグメント木の単位元
/// @fn apply 区間に作用を適用する @fn get 位置pの値を取得する
template <class F, F (*composition)(F, F), F (*id)()>
struct dual_segtree {
public:
/// @brief セグメント木を初期化する @param n サイズ
explicit dual_segtree(int n) : dual_segtree(std::vector<F>(n, id())) {}
/// @brief セグメント木を初期化する @param v vector<F>型の配列
explicit dual_segtree(const std::vector<F> &v) : _n(int(v.size())) {
log = ceil_pow2(_n);
size = 1 << log;
lz = std::vector<F>(2 * size, id());
for (int i = 0; i < _n; i++) lz[size + i] = v[i];
}
/// @brief [l, r) の要素に f を作用させます O(logN) @param l 左端 @param r 右端 @param f 作用素
void apply(int l, int r, F f) {
assert(0 <= l && l <= r && r <= _n);
if (l == r) return;
l += size;
r += size;
for (int i = log; i >= 1; i--) { // 遅延評価
if (((l >> i) << i) != l) push(l >> i); // lがiの倍数でない場合は、lを親に移動
if (((r >> i) << i) != r) push((r - 1) >> i); // rがiの倍数でない場合は、rを親に移動
}
while (l < r) {
if (l & 1) all_apply(l++, f); // lが奇数の場合は、lに作用を適用してからlをインクリメント
if (r & 1) all_apply(--r, f); // rが奇数の場合は、rをデクリメントしてからrに作用を適用
l >>= 1; // lを親に移動
r >>= 1; // rを親に移動
}
}
/// @brief 位置pの値を取得する @param p 位置
F get(int p) {
assert(0 <= p && p < _n);
p += size;
for (int i = log; i >= 1; i--) push(p >> i);
return lz[p];
}
private:
int _n, size, log;
std::vector<F> lz;
/// @brief 作用素を遅延評価する @param i 位置 @param f 作用素
void all_apply(int i, F f) {
lz[i] = composition(f, lz[i]);
}
/// @brief 作用素を遅延評価する @param i 位置
void push(int i) {
assert(i < size);
all_apply(2 * i, lz[i]);
all_apply(2 * i + 1, lz[i]);
lz[i] = id();
}
};
// ----- segment trees by @rrrrikiOW -----
/**
* @brief 二部グラフ構造体
*
* 使い方
*
* - BipartiteGraph(g):= gの二部グラフを作成
*
* - is_bipartitte():= 二部グラフかどうかを返す
*
* - operator\[\](i):= i番目の頂点の色を返す
*
*/
struct BipartiteGraph : dsu {
/**
* @brief コンストラクタ
* @tparam GraphType グラフの型
* @param g グラフのインスタンス
*
* グラフを受け取り、二部グラフの判定を行います。
* 結果は `is_bipartite` に格納されます。
*/
template <typename GraphType>
BipartiteGraph(const GraphType &g)
: dsu(g.size() * 2), color(g.size() * 2, -1), colored(false) {
is_bipartite_flag = bipartite(g);
}
/**
* @brief 二部グラフかどうかを返す関数
* @return 二部グラフであれば true、そうでなければ false
*/
inline bool is_bipartite() { return is_bipartite_flag; }
/**
* @brief 二部グラフの彩色を行う関数
* @return 彩色が可能であれば true、そうでなければ false
*
* グラフが二部グラフである場合に、各連結成分に対して色を割り当てます。
* この関数は内部で使用され、`operator[]` から呼び出されます。
*/
bool bipartite_graph_coloring() {
int n = color.size() / 2;
for (int i = 0; i < n; ++i) {
int a = leader(i);
int b = leader(i + n);
if (a == b) return false;
if (color[a] == -1) {
color[a] = 0;
color[b] = 1;
}
}
return true;
}
/**
* @brief 指定した頂点の色を取得する演算子オーバーロード
* @param i 頂点のインデックス
* @return 頂点の色（0または1）
*
* 頂点の色が未割り当ての場合、彩色を行う
*/
int operator[](int i) {
if (!colored) {
colored = true;
bipartite_graph_coloring();
}
return color[leader(i)];
}
private:
/// 各頂点の色を格納するベクター（0または1）
vector<int> color;
/// グラフが二部グラフかどうかを保持するフラグ
bool is_bipartite_flag;
/// 彩色済みかどうかを保持するフラグ
bool colored;
/**
* @brief 二部グラフかどうかを判定する関数
* @tparam GraphType グラフの型
* @param g グラフのインスタンス
* @return 二部グラフであれば true、そうでなければ false
*/
template <typename GraphType>
bool bipartite(const GraphType &g) {
int n = g.size();
for (int i = 0; i < n; ++i) {
for (const auto &e : g[i]) {
merge(e.from, e.to + n);
merge(e.to, e.from + n);
}
}
for (int v = 0; v < n; ++v) {
if (same(v, v + n)) {
return false;
}
}
return true;
}
};
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tag_and_trait.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
/**
* @brief 昇順ordered_set, 降順の時は-1をかけること
*
* 使い方
*
* - ordered_set_less<int> st; := int型の昇順ordered_setを宣言
*
* - st.insert(x); := xを挿入
*
* - st.erase(x); := xを削除
*
* - st.order_of_key(x); := xより小さい要素の個数を求める
*
* - *st.find_by_order(k); := k番目の要素を求める (0-indexed)
*
* - st.lower_bound(x); := x以上の最小の要素を求める
*
* - st.upper_bound(x); := xより大きい最小の要素を求める
*
* - st.size(); := 要素数を求める
*/
template <typename T>
using ordered_set_less = tree<T, null_type, std::less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#endif
/*
******* 神龜雖壽 *******
******* 猶有竟時 *******
******* 騰蛇乘霧 *******
******* 終爲土灰 *******
******* 老驥伏櫪 *******
******* 志在千里 *******
******* 烈士暮年 *******
******* 壯心不已 *******
******* 盈縮之期 *******
******* 不但在天 *******
******* 養怡之福 *******
******* 可得永年 *******
******* 幸甚至哉 *******
******* 歌以詠志 *******
*/