#950969 (C++17) No.1326 ふたりのDominator

提出ソース
結果

問題	No.1326 ふたりのDominator
ユーザー	Coki628
提出日時	2024-02-16 19:27:18
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	160 ms / 2,000 ms
コード長	36,643 bytes
コンパイル時間	4,788 ms
コンパイル使用メモリ	262,832 KB
実行使用メモリ	40,172 KB
最終ジャッジ日時	2024-02-16 19:27:27
合計ジャッジ時間	8,535 ms
ジャッジサーバーID （参考情報）	judge15 / judge13
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,676 KB
testcase_01	AC	2 ms 6,676 KB
testcase_02	AC	3 ms 6,676 KB
testcase_03	AC	2 ms 6,676 KB
testcase_04	AC	2 ms 6,676 KB
testcase_05	AC	2 ms 6,676 KB
testcase_06	AC	2 ms 6,676 KB
testcase_07	AC	3 ms 6,676 KB
testcase_08	AC	3 ms 6,676 KB
testcase_09	AC	3 ms 6,676 KB
testcase_10	AC	4 ms 6,676 KB
testcase_11	AC	3 ms 6,676 KB
testcase_12	AC	136 ms 28,704 KB
testcase_13	AC	136 ms 28,676 KB
testcase_14	AC	132 ms 28,688 KB
testcase_15	AC	135 ms 28,492 KB
testcase_16	AC	131 ms 27,360 KB
testcase_17	AC	107 ms 22,220 KB
testcase_18	AC	108 ms 17,440 KB
testcase_19	AC	82 ms 18,624 KB
testcase_20	AC	140 ms 38,632 KB
testcase_21	AC	139 ms 38,540 KB
testcase_22	AC	160 ms 40,172 KB
testcase_23	AC	99 ms 24,676 KB
testcase_24	AC	132 ms 28,700 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")

#define CONSTANTS
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;

constexpr long long INF = 1e18;
// constexpr long long INF = LONG_LONG_MAX;
// constexpr int MOD = 1000000007;
constexpr int MOD = 998244353;
constexpr long double EPS = 1e-10;
constexpr long double PI = M_PI;

using ll = long long; using ull = unsigned long long; using ld = long double; using pll = pair<ll, ll>; using pii = pair<int, int>; using pli = pair<ll, int>; using pil = pair<int, ll>; template<typename T> using vv = vector<vector<T>>; using vvl = vv<ll>; using vvi = vv<int>; using vvpll = vv<pll>; using vvpli = vv<pli>; using vvpil = vv<pil>;
#define name4(i, a, b, c, d, e, ...) e
#define rep(...) name4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)
#define rep1(i, a) for (ll i = 0, _aa = a; i < _aa; i++)
#define rep2(i, a, b) for (ll i = a, _bb = b; i < _bb; i++)
#define rep3(i, a, b, c) for (ll i = a, _bb = b; (c > 0 && a <= i && i < _bb) or (c < 0 && a >= i && i > _bb); i += c)
#define rrep(i, a, b) for (ll i=(a); i>(b); i--)
#define pb push_back
#define eb emplace_back
#define mkp make_pair
#define ALL(A) begin(A), end(A)
#define UNIQUE(A) sort(ALL(A)), A.erase(unique(ALL(A)), A.end())
#define elif else if
#define tostr to_string
#ifndef CONSTANTS
constexpr ll INF = 1e18; constexpr int MOD = 1000000007; constexpr ld EPS = 1e-10; constexpr ld PI = M_PI;
#endif
template<int mod> struct ModInt { int x = 0; ModInt() : x(0) {} ModInt(int64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {} ModInt(string s) { auto res = 0LL; for(auto &c : s){ assert(isdigit(c)); int d = c - '0'; res = (res * 10 + d) % mod; } x = res; } static int get_mod() { return mod; } ModInt &operator++() { x++; if (x == mod) x = 0; return *this; } ModInt &operator--() { if (x == 0) x = mod; x--; return *this; } ModInt &operator+=(const ModInt &p) { if ((x += p.x) >= mod) x -= mod; return *this; } ModInt &operator-=(const ModInt &p) { if ((x += mod - p.x) >= mod) x -= mod; return *this; } ModInt &operator*=(const ModInt &p) { x = (int)(1LL * x * p.x % mod); return *this; } ModInt &operator/=(const ModInt &p) { *this *= p.inv(); return *this; } ModInt operator++(int) { ModInt result = *this; ++*this; return result; } ModInt operator--(int) { ModInt result = *this; --*this; return result; } ModInt operator-() const { return ModInt(-x); } ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; } ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; } ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; } ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; } bool operator==(const ModInt &p) const { return x == p.x; } bool operator!=(const ModInt &p) const { return x != p.x; } bool operator<(const ModInt &p) const { return x < p.x; } ModInt inv() const { int a = x, b = mod, u = 1, v = 0, t; while (b > 0) { t = a / b; swap(a -= t * b, b); swap(u -= t * v, v); } return ModInt(u); } ModInt pow(int64_t n) const { ModInt ret(1), mul(x); while (n > 0) { if (n & 1) ret *= mul; mul *= mul; n >>= 1; } return ret; } friend ostream &operator<<(ostream &os, const ModInt &p) { return os << p.x; } friend istream &operator>>(istream &is, ModInt &a) { int64_t t; is >> t; a = ModInt<mod>(t); return (is); } explicit operator int() const { return x; } explicit operator ll() const { return x; } };
using mint = ModInt<MOD>;
template<typename T> int bisect_left(const vector<T> &A, T val, int lo = 0) { return lower_bound(A.begin() + lo, A.end(), val) - A.begin(); } template<typename T> int bisect_right(const vector<T> &A, T val, int lo = 0) { return upper_bound(A.begin() + lo, A.end(), val) - A.begin(); }
template<typename T> struct Compress { int N; vector<T> dat; bool built = false; Compress() {} Compress(const vector<T> &A) : dat(A) { build(); } void build() { sort(dat.begin(), dat.end()); dat.erase(unique(dat.begin(), dat.end()), dat.end()); N = dat.size(); built = true; } void add(T x) { assert(not built); dat.eb(x); } template<typename... Ts> void add(const T val, Ts... ts) { dat.eb(val); if constexpr (sizeof...(Ts) > 0) { add(ts...); } } void add(const vector<T> &A) { for (auto a : A) { add(a); } } int zip(T x) { assert(built); return bisect_left(dat, x); } T unzip(int x) { assert(built); return dat[x]; } int operator[](T x) { return zip(x); } int size() { assert(built); return dat.size(); } vector<ll> zip(const vector<T> &A) { int M = A.size(); vector<ll> res(M); rep(i, M) res[i] = zip(A[i]); return res; } };
template<typename T> map<T, ll> Counter(const vector<T> &A) { map<T, ll> res; for (T a : A) { res[a]++; } return res; } template<typename T> vector<ll> Counter(const vector<T> &A, int mx) { vector<ll> res(mx + 1); for (T a : A) { res[a]++; } return res; } map<char, ll> Counter(const string &S) { map<char, ll> res; for (char c : S) { res[c]++; } return res; } template<typename T> vector<pair<ll, T>> most_common(const map<T, ll> &C) { vector<pair<ll, T>> res; for (auto [k, v] : C) { res.eb(v, k); } sort(res.rbegin(), res.rend()); return res; }
template<typename T> vector<pair<T, int>> RLE(const vector<T> &A) { if (A.empty()) return {}; int N = A.size(); vector<pair<T, int>> res; T cur = A[0]; int cnt = 1; rep(i, 1, N) { if (A[i] == A[i - 1]) { cnt++; } else { res.pb({cur, cnt}); cnt = 1; cur = A[i]; } } res.pb({cur, cnt}); return res; } vector<pair<char, int>> RLE(const string &S) { if (S.empty()) return {}; int N = S.size(); vector<pair<char, int>> res; char cur = S[0]; int cnt = 1; rep(i, 1, N) { if (S[i] == S[i - 1]) { cnt++; } else { res.pb({cur, cnt}); cnt = 1; cur = S[i]; } } res.pb({cur, cnt}); return res; }
template<typename F> ll bisearch_min(ll mn, ll mx, const F &func) { ll ok = mx; ll ng = mn; while (ng + 1 < ok) { ll mid = (ok + ng) / 2; if (func(mid)) { ok = mid; } else { ng = mid; } } return ok; } template<typename F> ll bisearch_max(ll mn, ll mx, const F &func) { ll ok = mn; ll ng = mx; while (ok + 1 < ng) { ll mid = (ok + ng) / 2; if (func(mid)) { ok = mid; } else { ng = mid; } } return ok; }
int bit_length(ll x) { int res = 0; while (x) { res++; x /= 2; } return res; }
template<typename T> T ceil(T a, T b) { if (a >= 0) return (a + b - 1) / b; else return a / b; }
template<typename T> bool chmax(T &x, T y) { return (y > x) ? x = y, true : false; }
template<typename T> bool chmin(T &x, T y) { return (y < x) ? x = y, true : false; }
template<typename T, typename... Ts> vector<T> concat(const vector<T> &A, const vector<T> &B, Ts... args) { vector<T> res = A; res.insert(res.end(), B.begin(), B.end()); if constexpr (sizeof...(Ts) == 0) { return res; } else { return concat(res, args...); } }
template<typename T> pair<T, T> divmod(T a, T b) { T d = a / b; T m = a % b; return {d, m}; }
template<typename T1, typename T2> istream &operator>>(istream &is, pair<T1, T2> &p) { is >> p.first >> p.second; return is; } template<typename T> istream &operator>>(istream &is, vector<T> &v) { for (T &in : v) is >> in; return is; } template<typename T = ll> vector<T> LIST(int N) { vector<T> A(N); rep(i, N) { cin >> A[i]; } return A; }
string to_string(const string &S) { return S; } string to_string(char c) { return {c}; } template<typename T1, typename T2> string to_string(pair<T1, T2> p) { return to_string(p.first) + " " + to_string(p.second); }
template<typename T> string join(const vector<T> &A, string separator = "") { int N = A.size(); string res; rep(i, N) { res += tostr(A[i]); if (i != N - 1) res += separator; } return res; }
template<typename... Ts> auto listnd(size_t N, Ts... ts) { if constexpr (sizeof...(ts) == 1) { return vector<Ts...>(N, ts...); } else { auto res = listnd(ts...); return vector<decltype(res)>(N, res); } } template<typename T>[[deprecated("list2d will be merged with listnd")]] vv<T> list2d(int N, int M, T init) { return listnd(N, M, init); } template<typename T>[[deprecated("list3d will be merged with listnd")]] vv<vector<T>> list3d(int N, int M, int L, T init) { return listnd(N, M, L, init); } template<typename T>[[deprecated("list4d will be merged with listnd")]] vv<vv<T>> list4d(int N, int M, int L, int O, T init) { return listnd(N, M, L, O, init); }
template<typename T> T max(const vector<T> &A) { assert(not A.empty()); return *max_element(ALL(A)); } template<typename key, typename val> val max(const map<key, val> &mp) { val res = numeric_limits<val>::min(); for (auto &[k, v] : mp) chmax(res, v); return res; }
template<typename T> T min(const vector<T> &A) { assert(not A.empty()); return *min_element(ALL(A)); } template<typename key, typename val> val min(const map<key, val> &mp) { val res = numeric_limits<val>::max(); for (auto &[k, v] : mp) chmin(res, v); return res; }
template<typename T> T modulo(T a, T b) { return ((a % b) + b) % b; }
template<typename T> bool mul_overflow(T x, T y) { T z; return __builtin_mul_overflow(x, y, &z); } template<typename T> bool add_overflow(T x, T y) { T z; return __builtin_add_overflow(x, y, &z); }
template<class T, class U> inline pair<T, U> &operator+=(pair<T, U> &a, const pair<T, U> &b) { a.fi += b.fi; a.se += b.se; return a; } template<class T, class U> inline pair<T, U> &operator-=(pair<T, U> &a, const pair<T, U> &b) { a.fi -= b.fi; a.se -= b.se; return a; } template<class T, class U> inline pair<T, U> &operator*=(pair<T, U> &a, const pair<T, U> &b) { a.fi *= b.fi; a.se *= b.se; return a; } template<class T, class U> inline pair<T, U> &operator/=(pair<T, U> &a, const pair<T, U> &b) { a.fi /= b.fi; a.se /= b.se; return a; } template<class T, class U> constexpr void operator++(pair<T, U> &a, int) noexcept { a.first++; a.second++; } template<class T, class U> constexpr void operator--(pair<T, U> &a, int) noexcept { a.first--; a.second--; }
int popcount(ll S) { return __builtin_popcountll(S); }
ll pow(ll x, ll n) { ll res = 1; rep(_, n) res *= x; return res; } ll pow(int x, ll n) { return pow((ll)x, n); } ll pow(ll x, int n) { return pow(x, (ll)n); } ll pow(int x, int n) { return pow((ll)x, (ll)n); } template<typename T1, typename T2, typename M> T1 pow(T1 x, T2 n, M mod) { x %= mod; T1 res = 1; while (n > 0) { if (n & 1) { assert(not mul_overflow(res, x)); res = (res * x) % mod; } assert(not mul_overflow(x, x)); x = (x * x) % mod; n >>= 1; } return res; }
template<typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &p) { return os << p.first << ' ' << p.second; } template<class T, size_t... Is> void print_tuple(ostream &os, const T &arg, index_sequence<Is...>) { static_cast<void>(((os << (Is == 0 ? "" : " "), os << get<Is>(arg)), ...)); } template<class... Ts> ostream &operator<<(ostream &os, const tuple<Ts...> &arg) { print_tuple(os, arg, make_index_sequence<sizeof...(Ts)>()); return os; } template<typename T, size_t N> ostream &operator<<(ostream &os, const array<T, N> &arr) { rep(i, N) { os << arr[i]; if (i != (int)N - 1) { os << ' '; } } return os; } template<typename T, size_t N> void print(const array<T, N> &arr, string sep = " ") { rep(i, N) { cout << arr[i]; if (i != (int)N - 1) cout << sep; } cout << '\n'; } template<typename T> ostream &operator<<(ostream &os, const vector<T> &vec) { rep(i, vec.size()) { os << vec[i]; if (i != (int)vec.size() - 1) { os << ' '; } } return os; } template<typename T> void print(const vector<T> &vec, string sep = " ") { rep(i, vec.size()) { cout << vec[i]; if (i != (int)vec.size() - 1) cout << sep; } cout << '\n'; } template<typename T> void print(const deque<T> &que, string sep = " ") { vector<T> vec(ALL(que)); print(vec, sep); } template<typename T> void print(const set<T> &se, string sep = " ") { vector<T> vec(ALL(se)); print(vec, sep); } template<typename T> void print(const initializer_list<T> &li, string sep = " ") { vector<T> V(ALL(li)); print(V, sep); } void print() { cout << '\n'; } template<typename T> void print(T out) { cout << out << '\n'; }
#define debug(...) multi_debug(#__VA_ARGS__, __VA_ARGS__)
template<typename T> void multi_debug(string name, const vv<T> &grid) { cerr << name << ":" << endl; int H = grid.size(); int W = grid[0].size(); vector<int> mxlen(W); rep(h, H) { rep(w, W) { chmax(mxlen[w], (int)tostr(grid[h][w]).size()); } } rep(h, H) { rep(w, W) { int pad = mxlen[w] - (int)tostr(grid[h][w]).size(); cerr << string(pad, ' ') << grid[h][w]; if (w == W - 1) { cerr << endl; } else { cerr << ' '; } } } } template<class Tp, class... Ts> void multi_debug(string names, Tp arg, Ts... args) { if constexpr (sizeof...(Ts) == 0) { while (names.back() == ' ') { names.pop_back(); } cerr << names << ": " << arg << endl; } else { int n = names.size(), comma_pos = -1, paren_depth = 0, inside_quote = false; rep(i, n) { if (not inside_quote and paren_depth == 0 and names[i] == ',') { comma_pos = i; break; } if (names[i] == '\"' or names[i] == '\'') { if (i > 0 and names[i - 1] == '\\') continue; inside_quote ^= true; } if (not inside_quote and names[i] == '(') { paren_depth++; } if (not inside_quote and names[i] == ')') { paren_depth--; } } assert(comma_pos != -1); string name = names.substr(0, comma_pos); while (name.back() == ' ') { name.pop_back(); } cerr << name << ": " << arg << endl; int next_begin_at = comma_pos + 1; while (names[next_begin_at] == ' ') { next_begin_at++; } names = names.substr(next_begin_at); multi_debug(names, args...); } } template<typename T> void print(const vector<T> &V, char sep) { print(V, string{sep}); } template<typename T, size_t N> void print(const array<T, N> &arr, char sep) { print(arr, string{sep}); }
template<typename T> vector<T> reversed(vector<T> A) { reverse(ALL(A)); return A; } string reversed(string S) { reverse(ALL(S)); return S; }
template<typename T> vector<T> sorted(vector<T> A, bool reverse = false) { sort(ALL(A)); if (reverse) std::reverse(ALL(A)); return A; } string sorted(string S, bool reverse = false) { sort(ALL(S)); if (reverse) std::reverse(ALL(S)); return S; }
ll toint(string s) { assert(s.size() < 20); ll res = 0; for (char &c : s) { res *= 10; res += c - '0'; } return res; } int toint(char num) { return num - '0'; }
vector<string> split(const string &S, char separator) { int N = S.size(); vector<string> res; string cur; rep(i, N) { if (S[i] == separator) { res.eb(cur); cur = ""; } else { cur += S[i]; } } if (cur.size()) res.eb(cur); return res; }
template<typename T> vector<T> subarray(const vector<T> &A, int l, int r) { return vector<T>(A.begin() + l, A.begin() + r); }
template<typename T> T sum(const vector<T> &A) { return accumulate(ALL(A), (T)0); } template<typename key, typename val> val sum(const map<key, val> &mp) { val res = 0; for (auto &[k, v] : mp) res += v; return res; }
char tochar(int num) { return '0' + num; }
string tolower(string s) { for (auto& c : s) { c = tolower(c); } return s; }
string toupper(string s) { for (auto& c : s) { c = toupper(c); } return s; }
template<typename T> constexpr void operator--(vector<T> &vec, int) noexcept { rep(i, vec.size()) vec[i]--; } template<typename T> constexpr void operator++(vector<T> &vec, int) noexcept { rep(i, vec.size()) vec[i]++; }
void Yes() { print("Yes"); } void No() { print("No"); } void YES() { print("YES"); } void NO() { print("NO"); } void YESNO(bool f) { print(f ? "YES" : "NO"); } void YesNo(bool f) { print(f ? "Yes" : "No"); } void yesno(bool f) { print(f ? "yes" : "no"); }
template<typename T1, typename T2> pair<vector<T1>, vector<T2>> zip(const vector<pair<T1, T2>> &A) { int N = A.size(); pair<vector<T1>, vector<T2>> res = {vector<T1>(N), vector<T2>(N)}; rep(i, N) { res.first[i] = A[i].first; res.second[i] = A[i].second; } return res; } template<typename T1, typename T2, typename T3> tuple<vector<T1>, vector<T2>, vector<T3>> zip(const vector<tuple<T1, T2, T3>> &A) { int N = A.size(); tuple<vector<T1>, vector<T2>, vector<T3>> res = { vector<T1>(N), vector<T2>(N), vector<T3>(N) }; rep(i, N) { get<0>(res)[i] = get<0>(A[i]); get<1>(res)[i] = get<1>(A[i]); get<2>(res)[i] = get<2>(A[i]); } return res; }
template<typename Mint> struct ModTools { private: int MAX; vector<Mint> _fact, _factinv, inv; public: ModTools(int mx) : MAX(++mx) { _fact.resize(MAX); _factinv.resize(MAX); inv.resize(MAX); _fact[0] = _fact[1] = 1; rep(i, 2, MAX) { _fact[i] = _fact[i - 1] * (Mint)i; } _factinv[MAX - 1] = (Mint)1 / _fact[MAX - 1]; rep(i, MAX - 2, -1, -1) { _factinv[i] = _factinv[i + 1] * (Mint)(i + 1); } rep(i, MAX - 1, 0, -1) { inv[i] = _factinv[i] * _fact[i - 1]; } } Mint div(Mint a, int b) { return a * inv[b]; } Mint fact(int x) { assert(x < MAX); return _fact[x]; } Mint factinv(int x) { assert(x < MAX); return _factinv[x]; } Mint nCr(int n, int r) { if (n < r or r < 0) return 0; r = min(r, n - r); Mint num = _fact[n]; Mint den = _factinv[r] * _factinv[n - r]; return num * den; } Mint nHr(int n, int r) { assert(r + n - 1 < MAX); return nCr(r + n - 1, r); } Mint nPr(int n, int r) { if (n < r or r < 0) return 0; return _fact[n] * _factinv[n - r]; } Mint double_factorial(int n) { if (n % 2 == 0) { int k = n / 2; return Mint(2).pow(k) * fact(k); } else { int k = (n + 1) / 2; return fact(2 * k) / Mint(2).pow(k) / fact(k); } } };
template<typename T> vv<T> combinations(const vector<T> &A, int N) { int M = A.size(); vv<T> res; auto rec = [&](auto &&f, vector<T> &cur, int x, int n) -> void { if (n == N) { res.pb(cur); return; } rep(i, x, M) { cur.pb(A[i]); f(f, cur, i + 1, n + 1); cur.pop_back(); } }; vector<T> cur; rec(rec, cur, 0, 0); return res; }
ll nC2(ll n) { if (n < 2) return 0; return n * (n - 1) / 2; }
template<typename T> vv<T> permutations(const vector<T> &A, int N = -1) { if (N == -1) N = A.size(); int M = A.size(); assert(N <= M); vv<T> comb; rep(bit, 1 << M) { if (popcount(bit) != N) continue; vector<T> res; rep(i, M) { if (bit >> i & 1) { res.pb(A[i]); } } comb.pb(res); } vv<T> res; for (auto &perm : comb) { sort(ALL(perm)); do { res.pb(perm); } while (next_permutation(ALL(perm))); } return res; }
struct UnionFind { int n, groupcnt; vector<int> par, rank, sz; vector<bool> tree; UnionFind(int n) : n(n) { build(); } UnionFind() {} UnionFind(const vector<int> &info) : n(info.size()) { build(); vvi adj(n); rep(i, n) { adj[info[i]].eb(i); } rep(i, n) { if (adj[i].size()) { rep(j, adj[i].size() - 1) { merge(adj[i][j], adj[i][j + 1]); } } } } void build() { par.assign(n, 0); rank.assign(n, 0); sz.assign(n, 1); tree.assign(n, true); rep(i, n) par[i] = i; groupcnt = n; } void resize(int _n) { n = _n; par.assign(n, 0); rank.assign(n, 0); sz.assign(n, 1); tree.assign(n, true); rep(i, n) par[i] = i; groupcnt = n; } virtual int find(int x) { if (par[x] == x) { return x; } else { par[x] = find(par[x]); return par[x]; } } template<typename F> int merge(int a, int b, F f) { int x = find(a); int y = find(b); if (x == y) { f(-1, y); tree[x] = false; return -1; } if (!tree[x] or !tree[y]) { tree[x] = tree[y] = false; } groupcnt--; if (rank[x] < rank[y]) { f(y, x); par[x] = y; sz[y] += sz[x]; return y; } else { f(x, y); par[y] = x; sz[x] += sz[y]; if (rank[x] == rank[y]) { rank[x]++; } return x; } } int merge(int a, int b) { return merge(a, b, [](int r, int ch) {}); } bool same(int a, int b) { return find(a) == find(b); } ll size(int x) { return sz[find(x)]; } int size() { return groupcnt; } bool is_tree(int x) { return tree[find(x)]; } set<int> get_roots() { set<int> res; rep(i, n) { res.insert(find(i)); } return res; } vector<int> get_info() { vector<int> res(n); rep(i, n) { res[i] = find(i); } return res; } };
const vector<pii> dir4 = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
#define directions dir4
ll gridtoid(ll i, ll j, ll W) { return i * W + j; }
pll idtogrid(ll id, ll W) { return divmod(id, W); }
template<typename _Tp> struct Deque : deque<_Tp> { using deque<_Tp>::deque; _Tp pop_front() { _Tp res = this->front(); deque<_Tp>::pop_front(); return res; } _Tp pop_back() { _Tp res = this->back(); deque<_Tp>::pop_back(); return res; } }; template<typename T> void print(const Deque<T> &que) { vector<T> V(que.begin(), que.end()); print(V); }
template<typename _Key> struct Multiset : multiset<_Key> { using multiset<_Key>::multiset; _Key front() { assert(this->size()); return *this->begin(); } _Key pop_front() { _Key res = this->front(); multiset<_Key>::erase(this->begin()); return res; } _Key back() { assert(this->size()); return *this->rbegin(); } _Key pop_back() { _Key res = this->back(); multiset<_Key>::erase(prev(this->end())); return res; } bool exist(_Key x) { return this->find(x) != this->end(); } auto erase(_Key x) { auto itr = this->find(x); assert(itr != this->end()); return multiset<_Key>::erase(itr); } }; template<typename T> void print(const Multiset<T> &se) { vector<T> V(se.begin(), se.end()); print(V); }
template<typename _Tp, typename _Sequence = vector<_Tp>, typename _Compare = less<typename _Sequence::value_type>> struct PriorityQueue : priority_queue<_Tp, _Sequence, _Compare> { using priority_queue<_Tp, _Sequence, _Compare>::priority_queue; _Tp pop() { _Tp res = this->top(); priority_queue<_Tp, _Sequence, _Compare>::pop(); return res; } };
template<typename _Key> struct Set : set<_Key> { using set<_Key>::set; _Key front() { assert(this->size()); return *this->begin(); } _Key pop_front() { _Key res = this->front(); this->erase(this->begin()); return res; } _Key back() { assert(this->size()); return *this->rbegin(); } _Key pop_back() { _Key res = this->back(); this->erase(prev(this->end())); return res; } }; template<typename T> void print(const Set<T> &se) { vector<T> V(se.begin(), se.end()); print(V); }
template<typename _Tp> struct Vector : vector<_Tp> { using vector<_Tp>::vector; _Tp pop() { _Tp res = this->back(); this->pop_back(); return res; } template<typename F> auto map(F f) { Vector<decltype(f(_Tp()))> res; for (auto &val : *this) { res.eb(f(val)); } return res; } }; template<typename T> void print(const Vector<T> &A) { vector<T> V(A.begin(), A.end()); print(V); }
template<typename _Key, typename _Tp> struct defaultdict : map<_Key, _Tp> { const _Tp init; defaultdict() : init(_Tp()) {}; defaultdict(_Tp init) : init(init) {} _Tp &operator[](const _Key &k) { if (this->count(k)) { return map<_Key, _Tp>::operator[](k); } else { return map<_Key, _Tp>::operator[](k) = init; } } _Tp &operator[](_Key &&k) { if (this->count(k)) { return map<_Key, _Tp>::operator[](k); } else { return map<_Key, _Tp>::operator[](k) = init; } } };
template<typename T> vector<T> divisors(T n) { vector<T> res; for (T i = 1; i * i <= n; i++) { if (n % i == 0) { res.eb(i); if (n / i != i) res.eb(n / i); } } return res; }
template<typename T> vector<pair<T, int>> factorize(T n) { vector<pair<T, int>> ret; for (T i = 2; i * i <= n; i++) { int cnt = 0; while (n % i == 0) { n /= i; cnt++; } if (cnt) ret.emplace_back(i, cnt); } if (n > 1) ret.emplace_back(n, 1); return ret; }
template<typename T> T gcd(T a, T b) { while (b) { T t = a % b; a = b; b = t; } return a; } template<typename T> T gcd(const vector<T> &A) { T res = 0; for (auto a : A) res = gcd(res, a); return res; }
template<typename T> T lcm(T x, T y) { return x / gcd(x, y) * y; } template<typename T> T lcm(const vector<T> &A) { T res = 1; for (auto a : A) res = lcm(res, a); return res; }
template<typename T> struct Accumulate { vector<T> dat; int N; bool built = false; Accumulate(int N) : N(N) { dat.resize(N); } Accumulate(const vector<T> &A) : N(A.size()), dat(A) { build(); } void set(int i, T a) { dat[i] = a; } void add(int i, T a) { dat[i] += a; } void build() { rep(i, N - 1) { dat[i + 1] += dat[i]; } dat.insert(dat.begin(), 0); built = true; } virtual T query(int l, int r) { assert(built); assert(0 <= l and l <= N and 0 <= r and r <= N); return dat[r] - dat[l]; } T get(int i) { return query(i, i + 1); } T operator[](int i) { return query(i, i + 1); } ll bisearch_fore(int l, int r, ll x) { if (l > r) return -1; ll l_sm = query(0, l); int ok = r + 1; int ng = l - 1; while (ng + 1 < ok) { int mid = (ok + ng) / 2; if (query(0, mid + 1) - l_sm >= x) { ok = mid; } else { ng = mid; } } if (ok != r + 1) { return ok; } else { return -1; } } ll bisearch_back(int l, int r, ll x) { if (l > r) return -1; ll r_sm = query(0, r + 1); int ok = l - 1; int ng = r + 1; while (ok + 1 < ng) { int mid = (ok + ng) / 2; if (r_sm - query(0, mid) >= x) { ok = mid; } else { ng = mid; } } if (ok != l - 1) { return ok; } else { return -1; } } };
template<typename T> class BIT { protected: int n; vector<T> dat; public: BIT() = default; explicit BIT(int n) : n(n) { dat.assign(n + 1, T()); } explicit BIT(const vector<T> &v) : BIT((int)v.size()) { build(v); } virtual void build(const vector<T> &v) { assert(n == (int)v.size()); for (int i = 1; i <= n; i++) { dat[i] = v[i - 1]; } for (int i = 1; i <= n; i++) { int j = i + (i & -i); if (j <= n) dat[j] += dat[i]; } } virtual T sum(int r) { T s = T(); for (; r > 0; r -= r & -r) { s += dat[r]; } return s; } virtual void add(int k, const T &x) { for (++k; k <= n; k += k & -k) { dat[k] += x; } } T query(int l, int r) { if (l >= r) return T(); return sum(r) - sum(l); } virtual T get(int i) { T s = this->dat[i + 1]; if (i & 1) { int j = i; i++; i -= i & -i; for (; j > i; j -= j & -j) { s -= this->dat[j]; } } return s; } void update(int i, T x) { add(i, x - this->get(i)); } T operator[](int i) { return this->get(i); } int size() { return n; } int bisearch_fore(int l, int r, T x) { if (l > r) return -1; assert(l >= 0 and r < n); x += query(0, l); int k = lower_bound(x); assert(l <= k); if (k > r) { return -1; } else { return k; } } int bisearch_back(int l, int r, T x) { if (l > r) return -1; assert(l >= 0 and r < n); T total = query(0, r + 1); if (total - x < 0) { return -1; } int k = upper_bound(total - x); assert(k <= r); if (k < l) { return -1; } else { return k; } } int lower_bound(T x) const { int i = 0; for (int k = 1 << (__lg(n) + 1); k > 0; k >>= 1) { if (i + k <= n && dat[i + k] < x) { x -= dat[i + k]; i += k; } } return i; } int upper_bound(T x) const { int i = 0; for (int k = 1 << (__lg(n) + 1); k > 0; k >>= 1) { if (i + k <= n && dat[i + k] <= x) { x -= dat[i + k]; i += k; } } return i; } }; template<typename T> ostream &operator<<(ostream &os, BIT<T> &bit) { rep(i, bit.size()) { os << bit[i]; if (i != bit.size() - 1) { os << ' '; } } return os; }
template<typename Monoid, typename F> struct SegmentTree { int sz, n; vector<Monoid> seg; const F f; const Monoid M1; SegmentTree(int n, const F f, const Monoid &M1) : n(n), f(f), M1(M1) { sz = 1; while (sz < n) sz <<= 1; seg.assign(2 * sz, M1); } SegmentTree(const F f, const Monoid &M1) : f(f), M1(M1) { } SegmentTree(const vector<Monoid> &A, const F f, const Monoid &M1) : f(f), M1(M1) { build(A); } void resize(int n) { this->n = n; sz = 1; while (sz < n) sz <<= 1; seg.resize(2 * sz, M1); } void clear() { seg.clear(); } void set(int k, const Monoid &x) { seg[k + sz] = x; } void build() { for (int k = sz - 1; k > 0; k--) { seg[k] = f(seg[2 * k], seg[2 * k + 1]); } } void build(const vector<Monoid> &A) { n = A.size(); resize(n); rep(i, n) set(i, A[i]); build(); } void update(int k, const Monoid &x) { k += sz; seg[k] = x; while (k >>= 1) { seg[k] = f(seg[2 * k], seg[2 * k + 1]); } } Monoid query(int a, int b) { Monoid L = M1, R = M1; for (a += sz, b += sz; a < b; a >>= 1, b >>= 1) { if (a & 1) L = f(L, seg[a++]); if (b & 1) R = f(seg[--b], R); } return f(L, R); } Monoid operator[](const int &k) const { return seg[k + sz]; } Monoid all() { return seg[1]; } int size() { return n; } template<typename C> int find_subtree(int a, const C &check, Monoid &M, bool type) { while (a < sz) { Monoid nxt = type ? f(seg[2 * a + type], M) : f(M, seg[2 * a + type]); if (check(nxt)) a = 2 * a + type; else M = nxt, a = 2 * a + 1 - type; } return a - sz; } template<typename C> int find_first(int a, const C &check) { Monoid L = M1; if (a <= 0) { if (check(f(L, seg[1]))) return find_subtree(1, check, L, false); return -1; } int b = sz; for (a += sz, b += sz; a < b; a >>= 1, b >>= 1) { if (a & 1) { Monoid nxt = f(L, seg[a]); if (check(nxt)) return find_subtree(a, check, L, false); L = nxt; ++a; } } return -1; } template<typename C> int find_last(int b, const C &check) { Monoid R = M1; if (b >= sz) { if (check(f(seg[1], R))) return find_subtree(1, check, R, true); return -1; } int a = sz; for (b += sz; a < b; a >>= 1, b >>= 1) { if (b & 1) { Monoid nxt = f(seg[--b], R); if (check(nxt)) return find_subtree(b, check, R, true); R = nxt; } } return -1; } }; template<typename Monoid, typename F> SegmentTree<Monoid, F> get_segment_tree(int N, const F &f, const Monoid &M1) { return {N, f, M1}; } template<typename Monoid, typename F> SegmentTree<Monoid, F> get_segment_tree(const F &f, const Monoid &M1) { return {f, M1}; } template<typename Monoid, typename F> SegmentTree<Monoid, F> get_segment_tree( const vector<Monoid> &A, const F &f, const Monoid &M1 ) { return {A, f, M1}; } template<typename Monoid, typename F> ostream &operator<<(ostream &os, SegmentTree<Monoid, F> &seg) { rep(i, seg.size()) { os << seg[i]; if (i != seg.size() - 1) { os << ' '; } } return os; }
string bin(ll x) { string res; while (x) { if (x & 1) { res += '1'; } else { res += '0'; } x >>= 1; } reverse(ALL(res)); if (res == "") res += '0'; return res; }
string zfill(string str, int len) { string zeros; int n = str.size(); rep(i, len - n) zeros += '0'; return zeros + str; }

struct HeavyLightDecomposition { public: int N; vvi nodes; vector<int> sz, in, out, head, rev, par, dep; int la(int v, int k) { while (1) { int u = head[v]; if (in[v] - k >= in[u]) return rev[in[v] - k]; k -= in[v] - in[u] + 1; v = par[u]; } } int lca(int u, int v) const { for (;; v = par[head[v]]) { if (in[u] > in[v]) swap(u, v); if (head[u] == head[v]) return u; } } int next(int u, int v, int k) { int d = dist(u, v); assert(d >= k); return la(v, d - k); } int dist(int u, int v) const { return dep[u] + dep[v] - 2 * dep[lca(u, v)]; } template<typename E, typename Q, typename F, typename S> E query( int u, int v, const E &ti, const Q &q, const F &f, const S &s, bool edge = false ) { E l = ti, r = ti; for (;; v = par[head[v]]) { if (in[u] > in[v]) swap(u, v), swap(l, r); if (head[u] == head[v]) break; l = f(q(in[head[v]], in[v] + 1), l); } return s(f(q(in[u] + edge, in[v] + 1), l), r); } template<typename E, typename Q, typename F> E query( int u, int v, const E &ti, const Q &q, const F &f, bool edge = false ) { return query(u, v, ti, q, f, f, edge); } template<typename Q> void update(int u, int v, const Q &q, bool edge = false) { for (;; v = par[head[v]]) { if (in[u] > in[v]) swap(u, v); if (head[u] == head[v]) break; q(in[head[v]], in[v] + 1); } q(in[u] + edge, in[v] + 1); } /* {parent, child} */ vector<pair<int, int>> compress(vector<int> &remark) { auto cmp = [&](int a, int b) { return in[a] < in[b]; }; sort(begin(remark), end(remark), cmp); remark.erase(unique(begin(remark), end(remark)), end(remark)); int K = (int)remark.size(); for (int k = 1; k < K; k++) remark.emplace_back(lca(remark[k - 1], remark[k])); sort(begin(remark), end(remark), cmp); remark.erase(unique(begin(remark), end(remark)), end(remark)); vector<pair<int, int>> es; stack<int> st; for (auto &k : remark) { while (!st.empty() && out[st.top()] <= in[k]) st.pop(); if (!st.empty()) es.emplace_back(st.top(), k); st.emplace(k); } return es; } explicit HeavyLightDecomposition(const vvi &nodes, int root = 0) : nodes(nodes), N(nodes.size()) { sz.assign(N, 0); in.assign(N, 0); out.assign(N, 0); head.assign(N, root); rev.assign(N, 0); par.assign(N, 0); dep.assign(N, 0); dfs_sz(root, -1, 0); int t = 0; dfs_hld(root, -1, t); } int operator[](int u) const { assert(0 <= u && u < N); return in[u]; } private: void dfs_sz(int idx, int p, int d) { dep[idx] = d; par[idx] = p; sz[idx] = 1; if (nodes[idx].size() && nodes[idx][0] == p) swap(nodes[idx][0], nodes[idx].back()); for (auto &to : nodes[idx]) { if (to == p) continue; dfs_sz(to, idx, d + 1); sz[idx] += sz[to]; if (sz[nodes[idx][0]] < sz[to]) swap(nodes[idx][0], to); } } void dfs_hld(int idx, int p, int &times) { in[idx] = times++; rev[in[idx]] = idx; for (auto &to : nodes[idx]) { if (to == p) continue; head[to] = (nodes[idx][0] == to ? head[idx] : to); dfs_hld(to, idx, times); } out[idx] = times; } };
struct LowLink { const vvi &g; int N; vector<int> ord, low, articulations, is_arti; vector<pair<int, int>> bridges; LowLink(const vvi &_g) : g(_g), N(g.size()), ord(N, -1), low(N, -1), is_arti(N) { for (int i = 0, k = 0; i < N; i++) { if (ord[i] == -1) { k = dfs(i, k, -1); } } sort(ALL(bridges)); } bool is_articulation(int u) { return is_arti[u]; } bool is_bridge(int u, int v) { if (u > v) swap(u, v); auto itr = lower_bound(ALL(bridges), pii{u, v}); return itr != bridges.end() and (*itr) == pii{u, v}; } bool has_articulation() { return articulations.size(); } bool has_bridge() { return bridges.size(); } vector<int> get_articulations() { return articulations; } vector<pii> get_bridges() { return bridges; } private: int dfs(int idx, int k, int par) { low[idx] = (ord[idx] = k++); int cnt = 0; bool arti = false, second = false; for (auto &to : g[idx]) { if (ord[to] == -1) { cnt++; k = dfs(to, k, idx); low[idx] = min(low[idx], low[to]); arti |= (par != -1) && (low[to] >= ord[idx]); if (ord[idx] < low[to]) { bridges.emplace_back(minmax(idx, (int)to)); } } else if (to != par || second) { low[idx] = min(low[idx], ord[to]); } else { second = true; } } arti |= par == -1 && cnt > 1; if (arti) { articulations.push_back(idx); is_arti[idx] = true; } return k; } };
struct BiConnectedComponents : LowLink { vector<int> used; vector<vector<pair<int, int>>> bc; vector<pair<int, int>> tmp; BiConnectedComponents(const vvi &_g) : LowLink(_g) { build(); } void build() { used.assign(this->g.size(), 0); for (int i = 0; i < (int)used.size(); i++) { if (!used[i]) dfs(i, -1); } } void dfs(int idx, int par) { used[idx] = true; for (auto &to : this->g[idx]) { if (to == par) continue; if (!used[to] || this->ord[to] < this->ord[idx]) { tmp.emplace_back(minmax<int>(idx, to)); } if (!used[to]) { dfs(to, idx); if (this->low[to] >= this->ord[idx]) { bc.emplace_back(); while (true) { auto e = tmp.back(); bc.back().emplace_back(e); tmp.pop_back(); if (e.first == min<int>(idx, to) && e.second == max<int>(idx, to)) { break; } } } } } } };
struct BlockCutTree { const vector<vector<int>> g; BiConnectedComponents bcc; vector<vector<int>> aux, groups; vector<int> idar, idcc, sz, is_arti; BlockCutTree(const vector<vector<int>> &_g) : g(_g), bcc(g) { build(); } void build() { auto ar = bcc.get_articulations(); idar.resize(g.size(), -1); idcc.resize(g.size(), -1); for (int i = 0; i < (int)ar.size(); i++) idar[ar[i]] = i; aux.resize(ar.size() + bcc.bc.size()); vector<int> last(g.size(), -1); for (int i = 0; i < (int)bcc.bc.size(); i++) { vector<int> st; for (auto &[u, v] : bcc.bc[i]) st.push_back(u), st.push_back(v); for (auto &u : st) { if (idar[u] == -1) idcc[u] = i + ar.size(); else if (last[u] != i) { add(i + ar.size(), idar[u]); last[u] = i; } } } sz.resize(aux.size()); is_arti.resize(aux.size()); groups.resize(aux.size()); for (int u = 0; u < g.size(); u++) { groups[this->id(u)].eb(u); sz[this->id(u)]++; if (idar[u] != -1) { is_arti[this->id(u)] = true; } } } vector<int> &operator[](int i) { return aux[i]; } int size() const { return aux.size(); } int size(int k) { return sz[k]; } int id(int i) { return idar[i] == -1 ? idcc[i] : idar[i]; } bool is_articulation(int k) { return is_arti[k]; } vector<vector<int>> get_nodes() { return aux; } vector<vector<int>> get_groups() { return groups; } private: void add(int i, int j) { if (i == -1 or j == -1) return; aux[i].push_back(j); aux[j].push_back(i); }; };

void solve() {
    ll N, M;
    cin >> N >> M;
    vvi nodes(N);
    rep(i, M) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        nodes[u].eb(v);
        nodes[v].eb(u);
    }

    BlockCutTree bct(nodes);
    ll N2 = bct.size();
    HeavyLightDecomposition hld(bct.aux);
    Accumulate<ll> acc(N2);
    rep(u, N2) {
        if (bct.is_articulation(u)) {
            acc.set(hld[u], 1);
        }
    }
    acc.build();
    ll Q;
    cin >> Q;
    rep(i, Q) {
        ll x, y;
        cin >> x >> y;
        x--, y--;

        x = bct.id(x), y = bct.id(y);
        ll res = hld.query(
            x,
            y,
            0LL,
            [&](ll a, ll b) { return acc.query(a, b); },
            [](ll a, ll b) { return a + b; }
        );
        if (bct.is_articulation(x)) res--;
        if (x != y and bct.is_articulation(y)) res--;
        print(res);
    }
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);

    // single test case
    solve();

    // multi test cases
    // int T;
    // cin >> T;
    // while (T--) solve();

    return 0;
}
yukicoder

結果

テストケース

ソースコード
