結果

問題 No.1254 補強への架け橋
ユーザー marurunn11
提出日時 2022-08-29 02:36:32
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 132 ms / 2,000 ms
コード長 35,198 bytes
コンパイル時間 15,196 ms
コンパイル使用メモリ 321,652 KB
最終ジャッジ日時 2025-02-06 23:25:30
ジャッジサーバーID
(参考情報)
judge4 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 123
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include "bits/stdc++.h"
#ifdef _MSC_VER
#include <intrin.h> //gcc__popcnt, umul128 include
#define __builtin_popcount __popcnt
#define __builtin_popcountll __popcnt64
// 1 0 (0 0 )
inline unsigned int __builtin_ctz(unsigned int x) { unsigned long r; _BitScanForward(&r, x); return r; }
inline unsigned int __builtin_ctzll(unsigned long long x) { unsigned long r; _BitScanForward64(&r, x); return r; }
// 2 leading 0 (0 32, 64 )
inline unsigned int __builtin_clz(unsigned x) { return (unsigned int)__lzcnt(x); }
inline unsigned int __builtin_clzll(unsigned long long x) { return (unsigned int)__lzcnt64(x); }
#pragma warning(disable : 4996)
#pragma intrinsic(_umul128)
#endif
//#include <atcoder/all>
//using namespace atcoder;
using namespace std;
//---------- ----------
//#include <boost/multiprecision/cpp_int.hpp>
//#include <boost/multiprecision/cpp_dec_float.hpp>
//using namespace boost::multiprecision;
typedef long long ll;
typedef long double ld;
#define int long long
#define LL128 boost::multiprecision::int128_t
#define LL boost::multiprecision::cpp_int
#define LD100 boost::multiprecision::cpp_dec_float_100
#define LD50 boost::multiprecision::cpp_dec_float_50
#define rep(i, n) for(long long i = 0; i < (n); ++i)
#define REP(i, s, n) for(long long i = (s); i < (n); ++i)
#define rrep(i, n) for(long long i = (n) - 1; i >= 0; --i)
#define sqrt(d) pow((ld) (d), 0.50)
#define PII pair<int, int>
#define MP make_pair
#define PB push_back
#define ALL(v) v.begin(), v.end()
constexpr int INF2 = std::numeric_limits<int>::max() / 2 - 10000000;
constexpr long long INF = std::numeric_limits<long long>::max() / 2 - 10000000;
const ld pi = acos(-1);
//constexpr int MOD = 1000000007; //1e9 + 7
constexpr int MOD = 998244353; // 7 * 17 * 2^23 + 1
//---------- chmax, min ----------
template<class T> inline void chmax(T& a, T b) {
if (a < b) a = b;
}
template<class T> inline void chmin(T& a, T b) {
if (a > b) a = b;
}
//---------- gcd, lcm ----------
template<typename T = long long>
T my_gcd(T a, T b) {
if (b == (T)0) return a;
return my_gcd<T>(b, a % b);
}
template<typename T = long long>
T my_lcm(T a, T b) {
return a / my_gcd<T>(a, b) * b;
}
// ax + by = gcd(a, b) gcd(a, b)
// a, b
long long my_gcd_ext(long long a, long long b, long long& x, long long& y) {
if (b == 0) {
x = 1; y = 0;
return a;
}
long long tempo = my_gcd_ext(b, a % b, y, x);
//bx' + ry' = gcd(a, b) → (qb + r)x + by = gcd(a, b) // (r = a % b)
//b(x' - qy') + (bq + r)y' = gcd(a, b)
// x = y', y = x' - qy'
y -= (a / b) * x;
return tempo;
}
// (CRT)
// x = base1 (mod m1) x = base2 (mod m2)
// (r, m) x = r (mod m) m = lcm(m1, m2)
// (0, -1)
pair<long long, long long> CRT(long long base1, long long m1, long long base2, long long m2) {
long long p, q;
long long gcd0 = my_gcd_ext(m1, m2, p, q);
if ((base2 - base1) % gcd0 != 0) return make_pair(0, -1);
long long lcm0 = m1 * (m2 / gcd0); //
p *= (base2 - base1) / gcd0;
p %= (m2 / gcd0);
//q *= (base2 - base1) / gcd0;
//q %= (m1 / gcd0);
long long r = (base1 + m1 * p) % lcm0;
if (r < 0) r += lcm0;
return make_pair(r, lcm0);
}
//M a gcd(a, M) = 1
long long my_invmod(long long a, long long M) {
long long x = 0, y = 0;
long long memo = my_gcd_ext(a, M, x, y);
assert(memo == 1LL);
x %= M;
if (x < 0) x += M;
return x;
}
//2 ()
//N^aM
template<typename T = long long>
constexpr T my_pow(T N, long long a, long long M) {
assert(0 <= a);
T x = N % M, res = (T)1;
while (a) {
if (a & 1) {
res *= x;
res %= M;
}
x *= x; // x *this (2)
x %= M;
a >>= 1;
}
return res;
}
// 2 ()
// T = modint
template<typename T = long long>
constexpr T my_pow(T N, long long a) {
assert(0 <= a);
T x = N, res = (T)1;
while (a) {
if (a & 1) res *= x;
x *= x; // x *this (2)
a >>= 1;
}
return res;
}
// base n iv.at(i)
vector<signed> ll_to_vector(signed base, long long n) {
long long tempo = n;
long long tempo2 = n; //使
signed n_digit = 1;
while (tempo2 >= base) {
tempo2 /= base;
n_digit++;
}
vector<signed> v(n_digit, 0); // v 調
long long denominator = my_pow<long long>((long long)base, (long long)(n_digit - 1));
for (signed i = 0; i < n_digit; i++) {
v.at(i) = tempo / denominator;
tempo -= v.at(i) * denominator;
denominator /= base;
}
return v;
}
// M 0 M
vector<signed> ll_to_vector(signed base, long long n, int M) {
vector<signed> v = ll_to_vector(base, n);
//assert((int)v.size() <= M);
if ((int)v.size() >= M) return v;
else {
int diff = M - v.size();
vector<signed> res(diff, 0);
for (int i = 0; i < (int)v.size(); i++) res.emplace_back(v.at(i));
return res;
}
}
//prime false O(n loglog n)
// T = int (defalt, sieve ll )
// vector<char>
template<typename T = int>
vector<bool> sieve_bool(T N) {
vector<bool> res(N + 1, true);
res.at(0) = false;
res.at(1) = false;
for (T i = 2; 2 * i <= N; i++) {
res.at(2 * i) = false;
}
for (T i = 3; i * i <= N; i += 2) {
//i false
if (res.at(i)) {
T j = i * i; // i^2 i false
while (j <= N) {
res.at(j) = false;
j += 2 * i;
}
}
}
return res;
};
// n + 1 vector res.at(i) i 1
// res.at(i) == i i != 0, 1 i
// 2e8 2.3 ~ 2.4 sec sieve_bool 0.7 sec 3 ll 3.2 sec
// T = int (defalt, sieve ll )
template<typename T = int>
vector<T> sieve(T n) {
n++; // n +1
vector<T> res(n, 0);
for (T i = 1; i < n; i++) {
if (i % 2 == 0) res.at(i) = 2; //
else res.at(i) = i; //
}
for (T i = 3; i * i < n; i += 2) {
//i i
if (res.at(i) == i) {
T j = i * i; // i^2 i
while (j < n) {
if (res.at(j) == j) res.at(j) = i;
j += 2 * i;
}
}
}
return res;
};
//O (sqrt(n))
constexpr bool is_prime(long long N) {
//
if (N == 1000000007 || N == 1000000009) return true;
if (N == 998244353 || N == 167772161 || N == 469762049 || N == 1224736769) return true; //g = 3;
if (N == 924844033 || N == 1012924417) return true; //g = 5;
if (N == 163577857) return true; //g = 23;
//
if (N <= 1) return false;
if (N == 2 || N == 3) return true;
if (N % 2 == 0) return false;
if (N % 3 == 0) return false;
for (long long i = 1; (6 * i + 1) * (6 * i + 1) <= N; ++i) {
if (N % (6 * i + 1) == 0) return false;
}
for (long long i = 0; (6 * i + 5) * (6 * i + 5) <= N; ++i) {
if (N % (6 * i + 5) == 0) return false;
}
return true;
}
template <int n> constexpr bool is_prime_constexpr = is_prime(n);
// (O(sqrt(N)) → O(N^0.25) ρ
// T = long long (defalt)
template<typename T = long long>
map<T, T> PrimeFactor(T N) {
map<T, T> res;
T i = 2;
while (i * i <= N) {
while (N % i == 0) {
res[i]++;
N /= i;
}
i += 1 + (i % 2); //i == 2 +1, +2
}
if (N > 1) res[N]++; //sqrt(( N)) 1
return res;
}
// sieve vector min_factor
// T = int (defalt, sieve ll )
template<typename T = int>
map<T, T> PrimeFactor2(T target, vector<T>& min_factor) {
map<T, T> res;
if (min_factor.empty() || (T)min_factor.size() - 1 < target) min_factor = sieve<T>(target);
while (target > 1) {
res[min_factor[target]]++;
target /= min_factor[target];
}
return res;
}
// O(sqrt(N))
vector<long long> count_dividers(long long target) {
vector <long long> dividers, tempo;
long long i = 1;
while (i * i < target + 1) {
if (target % i == 0) {
dividers.push_back(i);
if (i < target / i) tempo.push_back(target / i); // ifsqrt(target)
}
i++;
}
for (long long j = 0; j < (long long)tempo.size(); j++) {
dividers.push_back(tempo.at(tempo.size() - 1 - j));
}
return dividers;
}
// sieve vector min_factor
// T = int (defalt, sieve ll )
template<typename T = int>
vector<T> count_dividers2(T target, vector<T>& min_factor, bool is_sort = false) {
vector<T> dividers = { 1 };
map<T, T> memo = PrimeFactor2<T>(target, min_factor);
for (auto&& iter = memo.begin(); iter != memo.end(); iter++) {
vector <T> tempo = dividers;
for (T k = 0; k < (T)tempo.size(); k++) {
T times = 1;
for (T j = 1; j <= (iter->second); j++) {
times *= iter->first;
dividers.push_back(tempo[k] * times);
}
}
}
if (is_sort) sort(dividers.begin(), dividers.end()); //sort
return dividers;
}
class UnionFind {
public:
vector<int> parent;
vector<int> rank;
vector<int> v_size;
UnionFind(int N) : parent(N), rank(N, 0), v_size(N, 1) {
rep(i, N) {
parent[i] = i;
}
}
int root(int x) {
if (parent[x] == x) return x;
return parent[x] = root(parent[x]); //
}
void unite(int x, int y) {
int rx = root(x);
int ry = root(y);
if (rx == ry) return; //xy
if (rank[rx] < rank[ry]) {
parent[rx] = ry;
v_size[ry] += v_size[rx];
}
else {
parent[ry] = rx;
v_size[rx] += v_size[ry];
if (rank[rx] == rank[ry]) rank[rx]++;
}
}
bool same(int x, int y) {
return (root(x) == root(y));
}
int count_tree() {
int N = parent.size();
int res = 0;
rep(i, N) {
if (root(i) == i) res++;
}
return res;
}
int size(int x) {
return v_size[root(x)];
}
};
//
ld calc_dist(int x1, int y1, int x2, int y2) {
int tempo = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
ld res = sqrt((ld)tempo);
return res;
}
//
vector<pair<int, char>> RunLength(const string& S) {
int N = S.size();
vector<pair<int, char>> memo;
if (N == 1) {
memo.push_back(MP(1, S.at(0)));
return memo;
}
int tempo = 1;
for (int i = 1; i < N; i++) {
if (i != N - 1) {
if (S.at(i) == S.at(i - 1)) tempo++;
else {
memo.push_back(MP(tempo, S.at(i - 1)));
tempo = 1;
}
}
else {
if (S.at(i) == S.at(i - 1)) {
tempo++;
memo.push_back(MP(tempo, S.at(i - 1)));
}
else {
memo.push_back(MP(tempo, S.at(i - 1)));
memo.push_back(MP(1, S.at(i)));
}
}
}
return memo;
}
void printf_ld(ld res) {
printf("%.12Lf\n", res);
//cout << std::fixed << std::setprecision(12) << res << endl;
}
template<typename T = long long>
void print_vec(vector<T> v) {
int N = v.size();
rep(i, N) {
if (i != N - 1) cout << v.at(i) << " ";
else cout << v.at(i) << endl;
}
}
template<typename T = long long>
void print_vec(deque<T> v) {
int N = v.size();
rep(i, N) {
if (i != N - 1) cout << v.at(i) << " ";
else cout << v.at(i) << endl;
}
}
//mint mod
//m
// m is_prime
//※ constexpr const C++11
template<int m, typename T = long long> class mint {
private:
T _val;
public:
//---------- ----------
constexpr mint(T v = 0LL) noexcept : _val(v% m) {
if (_val < 0) _val += m;
}
constexpr T val() const noexcept {
return _val;
}
//------------------------------ ------------------------------
constexpr mint& operator += (const mint& r) noexcept {
_val += r._val;
if (_val >= m) _val -= m;
return *this;
}
constexpr mint& operator -= (const mint& r) noexcept {
_val -= r._val;
if (_val < 0) _val += m;
return *this;
}
constexpr mint& operator *= (const mint& r) noexcept {
_val *= r._val; _val %= m;
return *this;
}
constexpr mint& operator /= (const mint& r) noexcept {
if (!prime) {
//a * u + b * v = 1 gcd(a, m) == 1
T a = r._val, b = m, u = 1, v = 0;
while (b) {
T q = a / b;
a -= q * b; swap(a, b); // swap
u -= q * v; swap(u, v);
}
//assert(a == 1); //gcd(r._val, m) == 1;
_val *= u; _val %= m;
if (_val < 0) _val += m;
}
else {
// prime 使
*this *= r.modpow(m - 2);
}
return *this;
}
constexpr mint operator + (const mint& r) const noexcept { return mint(*this) += r; }
constexpr mint operator - (const mint& r) const noexcept { return mint(*this) -= r; }
constexpr mint operator * (const mint& r) const noexcept { return mint(*this) *= r; }
constexpr mint operator / (const mint& r) const noexcept { return mint(*this) /= r; }
constexpr bool operator == (const mint& r) const noexcept {
return this->_val == r._val;
}
constexpr bool operator != (const mint& r) const noexcept {
return this->_val != r._val;
}
//------------------------------ ------------------------------
//---------- ----------
constexpr mint operator ++() noexcept { this->_val++; if (this->_val == m) this->_val = 0; return mint(*this); }
constexpr mint operator --() noexcept { if (this->_val == 0) this->_val = m; this->_val--; return mint(*this); }
//---------- ----------
constexpr mint operator++(signed) noexcept { mint temp(_val); ++_val; if (_val == m) _val = 0; return temp; }
constexpr mint operator--(signed) noexcept { mint temp(_val); if (_val == 0) _val = m; --_val; return temp; }
constexpr mint operator -() const noexcept { return mint(-_val); }
//---------- ----------
friend constexpr ostream& operator << (ostream& os, const mint<m, T>& x) noexcept {
return os << x._val;
}
friend istream& operator >> (istream& is, mint<m, T>& x) noexcept {
T init_val;
is >> init_val;
x = mint<m, T>(init_val);
return is;
}
//---------- ----------
constexpr mint<m, T> inverse() const noexcept {
mint<m, T> e(1);
return e / (*this);
}
private:
// O(sqrt(m)) ; m 1e11
// Miller-Rabin 使
static constexpr bool prime = is_prime_constexpr<m>;
//---------- ----------
constexpr mint<m, T> modpow(long long n) const noexcept {
assert(0 <= n);
mint<m, T> x = *this, r = 1;
while (n) {
if (n & 1) r *= x;
x *= x; // x *this (2)
n >>= 1;
}
return r;
}
};
using modint = mint<MOD, long long>;
vector<modint> dp_fac;
vector<modint> dp_fac_inv;
// x!o(x).
template<typename T = modint>
void fac_initialize(int x, vector<T>& dp = dp_fac, vector<T>& dp_inv = dp_fac_inv) {
if ((int)dp.size() <= x) {
int n = dp.size(); if (n == 0) ++n;
dp.resize(x + 1, (T)1);
for (int i = n; i <= x; ++i) {
dp.at(i) = dp.at(i - 1) * i;
}
}
if ((int)dp_inv.size() <= x) {
int n = dp_inv.size();
dp_inv.resize(x + 1, (T)1);
dp_inv.at(x) /= dp.at(x);
for (int i = x - 1; i >= n; --i) {
dp_inv.at(i) = dp_inv.at(i + 1) * (i + 1);
}
}
}
// x ! dp ( dp_fac<modint>)
// long long vector<long long> 20 ! = 2.43e18 long long
template<typename T = modint>
T factorial(int x, vector<T>& dp = dp_fac) {
assert(x >= 0);
//
if ((int)dp.size() > x) {
return dp.at(x);
}
int n = dp.size();
//dp x + 1
for (int i = n; i < x + 1; i++) {
if (i == 0) dp.push_back((T)1);
else dp.push_back(dp.back() * i);
}
return dp.at(x);
}
template<typename T = modint>
T factorial_inv(int x, vector<T>& dp = dp_fac_inv) {
assert(x >= 0);
//
if ((int)dp.size() > x) {
return dp.at(x);
}
int n = dp.size();
//dp x + 1
for (int i = n; i < x + 1; i++) {
if (i == 0) dp.push_back((T)1);
else dp.push_back(dp.back() / i);
}
return dp.at(x);
}
// N_C_a
template<typename T = modint, typename U = int>
T my_comb(U N, U a, vector<T>& dp = dp_fac, vector<T>& dp_inv = dp_fac_inv) {
if (N < a) return (T)0;
T ans = factorial<T>(N, dp);
ans *= factorial_inv<T>(a, dp_inv);
ans *= factorial_inv<T>(N - a, dp_inv);
return ans;
}
// N_C_a (1)
template<typename T, typename U = int>
T my_comb2(U N, U a) {
if (N < a) return (T)0;
T answer = 1;
for (U i = (U)0; i < a; i++) {
answer *= (N - i);
answer /= i + 1;
}
return answer;
}
ld now_clock() {
ld t = (ld)clock() / (ld)CLOCKS_PER_SEC;
return t;
}
//
const vector<int> vdh = { 1, -1, 0, 0 };
const vector<int> vdw = { 0, 0, 1, -1 };
// ()
// add_edge, add_biedge ()
// bfs01, dijkstra ()
// route ()
// cnt_route () → ABC 021 C -
// from_grid(const vector<string>& S); grid
// Kruskal (UnionFind ), Prim (MST) ()
// bfsTopSort ()
// IsClosed() 1()
// bfs_tree(int root), dfs_tree(int root) bfsdfs()
template<typename T = long long>
struct edge {
int to;
T weight;
int index; //
constexpr bool operator < (const edge& r) const noexcept {
if (weight != r.weight) return (weight < r.weight);
else return (index < r.index);
}
constexpr bool operator > (const edge& r) const noexcept {
if (weight != r.weight) return (weight > r.weight);
else return (index > r.index);
}
};
template<typename T> bool operator== (const edge<T>& a, const edge<T>& b) { return (a.to == b.to && a.weight == b.weight && a.index == b.index); };
template<typename T = long long>
struct edge2 {
int from;
int to;
T weight;
constexpr bool operator < (const edge2& r) const noexcept {
if (weight != r.weight) return (weight < r.weight);
else return (from < r.from);
}
};
template<typename T = long long>
class graph {
int sp = -1; //
public:
vector<vector<edge<T>>> G;
vector<edge2<T>> edges;
vector<T> dist; //
vector<int> prev; //
vector<int> prev_edge; //
graph(int _n) : N(_n) { initialize(_n); };
graph() : N(0) {};
// G
void add_edge(int from, int to, T weight = (T)1) {
assert(0 <= from && from < N);
assert(0 <= to && to < N);
assert((T)0 <= weight);
G.at(from).emplace_back(edge<T>{ to, weight, (int)edges.size() });
edges.push_back(edge2<T>{from, to, weight});
}
// G
void add_biedge(int from, int to, T weight = (T)1) {
add_edge(from, to, weight);
add_edge(to, from, weight);
}
// (01-BFS / weight 0 or 1 使 / )
void bfs01(vector<int> vs) {
const T ini_dist = -1;
//assert(!vs.empty());
deque<int> que;
dist.assign(N, ini_dist);
prev.assign(N, -1);
prev_edge.assign(N, -1);
for (auto&& s : vs) {
assert(0 <= s && s < N);
que.push_front(s); dist.at(s) = 0;
}
while (!que.empty()) {
int v = que.front(); que.pop_front();
for (edge<T> e : G.at(v)) {
int nextv = e.to;
//if cost = 0 cost = 1
if (dist.at(nextv) != ini_dist && dist.at(nextv) <= dist.at(v) + e.weight) continue;
dist.at(nextv) = dist.at(v) + e.weight;
if ((int)vs.size() == 1) {
prev.at(nextv) = v;
prev_edge.at(nextv) = e.index;
}
if (e.weight) que.push_back(nextv);
else que.push_front(nextv);
}
}
}
// (01-BFS / weight 0 or 1 使 / )
void bfs01(int s) {
vector<int> vs = { s };
sp = s;
bfs01(vs);
}
// dijkstra (, prev, prev_edge )
void dijkstra(int s) {
assert(0 <= s && s < N);
sp = s;
dist.assign(N, INF);
prev.assign(N, -1);
prev_edge.assign(N, -1);
//first second
priority_queue<pair<T, int>, vector<pair<T, int>>, greater<pair<T, int>>> que;
dist.at(s) = (T)0; que.push(make_pair((T)0, s));
while (!que.empty()) {
pair<T, int> p = que.top(); que.pop();
int v = p.second;
if (dist.at(v) < p.first) continue; //
for (int i = 0; i < (int)G.at(v).size(); i++) {
edge<T> e = G.at(v).at(i);
if (dist.at(e.to) > dist.at(v) + e.weight) {
dist.at(e.to) = dist.at(v) + e.weight;
prev.at(e.to) = v;
prev_edge.at(e.to) = e.index;
que.push(make_pair(dist.at(e.to), e.to));
}
}
}
}
// sp dist sp v
// first , second
// sp v
pair<vector<int>, vector<int>> route(int v) {
assert(sp != -1);
vector<int> res = { v }; //
vector<int> es;
while (res.back() != sp) {
int now = res.back();
int next_v = prev.at(now);
res.push_back(next_v);
es.push_back(prev_edge.at(now));
}
reverse(res.begin(), res.end());
return { res, es };
}
// sp dist
// sp i
template<typename U = modint>
U cnt_route(int i, vector<U>& cnt, vector<bool>& seen) {
assert(sp != -1);
assert((int)cnt.size() == N);
assert((int)seen.size() == N);
if (seen.at(i)) return cnt.at(i);
else if (i == sp) {
seen.at(i) = true;
return cnt.at(i) = (U)1;
}
else {
U sum = 0;
for (auto& e : G.at(i)) {
int nextv = e.to;
if (dist.at(i) == dist.at(nextv) + e.weight) {
sum += cnt_route(nextv, cnt, seen);
}
}
seen.at(i) = true;
return cnt.at(i) = sum;
}
}
// grid
void from_grid(const vector<string>& S) {
assert(!S.empty());
int H = S.size();
int W = S.at(0).size();
int N = H * W;
initialize(N);
for (int h = 0; h < H; ++h) {
for (int w = 0; w < W; ++w) {
for (int i = 0; i < (int)vdh.size(); ++i) {
int dh = vdh.at(i), dw = vdw.at(i);
if (h + dh < 0 || H <= h + dh) continue;
if (w + dw < 0 || W <= w + dw) continue;
int v = h * W + w;
int nextv = (h + dh) * W + (w + dw);
if (S.at(h + dh).at(w + dw) == '#') { //
continue;
}
else {
add_edge(v, nextv, 1);
}
}
}
}
}
// ()
//---------- Prim (MST, Minimum Spanning Tree) ----------
// sp ( N ) pair
template<typename U = T>
pair<U, int> Prim(int sp = 0) {
assert(0 <= sp && sp < N);
U sum = 0;
int marked_cnt = 0;
vector<bool> marked(N, false);
priority_queue<edge<T>, vector<edge<T>>, greater<edge<T>>> que;
// ----- ↓↓ -----
++marked_cnt;
marked[sp] = true;
for (auto&& e : G[sp]) que.push(e);
// ----- ↑↑ -----
while (marked_cnt < N && !que.empty()) {
auto e = que.top(); que.pop();
int nextv = e.to;
if (marked[nextv]) continue;
++marked_cnt;
marked[nextv] = true;
for (auto&& nexte : G[nextv]) que.push(nexte);
sum += e.weight;
}
return make_pair(sum, marked_cnt);
}
// ()
//---------- Kruskal (MST, Minimum Spanning Tree) ----------
//---------- UnionFind ----------
// first: INF
// second: ()
template<typename U = T>
pair<U, vector<edge2<T>>> Kruskal() {
assert(edges.size() % 2 == 0);
int E = edges.size() / 2;
vector<edge2<T>> es;
for (int i = 0; i < (int)edges.size(); i += 2) {
int v1 = edges.at(i).from;
int v2 = edges.at(i).to;
T w = edges.at(i).weight;
assert(edges.at(i + 1).from == v2);
assert(edges.at(i + 1).to == v1);
assert(edges.at(i + 1).weight == w);
es.push_back(edge2<T>{v1, v2, w});
}
std::sort(es.begin(), es.end());
U sum = 0;
vector<edge2<T>> vres;
UnionFind tree(N);
rep(i, E) {
edge2<T> e = es.at(i);
if (!tree.same(e.from, e.to)) {
tree.unite(e.from, e.to);
sum += e.weight;
vres.push_back(e);
}
}
//
rep(v, N) {
if (!tree.same(0, v)) return { INF, vector<edge2<T>>(0) };
}
return { sum, vres };
}
// .first;
// .second;
pair<bool, vector<int>> bfsTopSort() {
vector<int> CntIn(N, 0);
for (int i = 0; i < N; ++i) {
for (int j = 0; j < (int)G.at(i).size(); ++j) {
int v = G.at(i).at(j).to;
++CntIn.at(v);
}
}
vector<int> res;
queue<int> que;
//priority_queue<int, vector<int>, greater<int>> que; //
for (int i = 0; i < N; ++i) {
if (CntIn.at(i) == 0) {
que.push(i);
--CntIn.at(i);
}
}
while (!que.empty()) {
int v = que.front(); que.pop();
//int v = que.top(); que.pop(); //priority_que
res.push_back(v);
for (int i = 0; i < (int)G.at(v).size(); ++i) {
int next_v = G.at(v).at(i).to;
if (CntIn.at(next_v) == -1) {
//
return make_pair(false, vector<int>());
}
--CntIn.at(next_v);
if (CntIn.at(next_v) == 0) {
que.push(next_v);
}
}
}
if (res.size() == N) {
return make_pair(true, res);
}
else {
return make_pair(false, vector<int>());
}
}
//()
//first; bool
//second;
pair<bool, vector<int>> IsClosed() {
vector<bool> seen(N, false);
for (int v = 0; v < N; ++v) {
if (seen.at(v)) continue;
vector<int> vec;
bool flag = dfs_closed(v, -1, vec, seen);
if (flag) {
vector<int> res;
while (!vec.empty()) {
res.push_back(vec.back());
vec.pop_back();
if (res.size() > 1 && res.front() == res.back()) break;
}
assert((int)res.size() > 1);
return make_pair(true, res);
}
}
vector<int> vec;
return make_pair(false, vec);
}
//bfs ()
vector<pair<int, int>> bfs_tree(int root = 0) {
assert(0 <= root && root < N);
vector<pair<int, int>> res; //
vector<int> edge_index; //
queue<int> que;
que.push(root);
UnionFind uf(N);
while (!que.empty()) {
int v = que.front(); que.pop();
for (const auto& e : G.at(v)) {
int nv = e.to;
if (uf.same(root, nv)) continue;
uf.unite(root, nv);
que.push(nv);
res.push_back({ v, nv });
edge_index.push_back(e.index);
}
}
// ()
for (int i = 0; i < (int)edge_index.size(); ++i) edge_index.at(i) /= 2;
//sort(ALL(edge_index));
//print_vec(edge_index);
return res;
}
//dfs ()
//lowlink
// cross edge
vector<pair<int, int>> dfs_tree(int root = 0) {
assert(0 <= root && root < N);
vector<pair<int, int>> res; //
vector<int> edge_index; //
vector<bool> seen_v(N, false);
vector<bool> seen_e((int)edges.size(), false);
ord.assign(N, -1); //
lowlink.assign(N, -1);
int first_ptr = 0;
dfs_tree_func(root, res, edge_index, seen_v, seen_e, first_ptr);
// ()
for (int i = 0; i < (int)edge_index.size(); ++i) edge_index.at(i) /= 2;
//sort(ALL(edge_index));
//print_vec(edge_index);
return res;
}
//dfs
bool IsBridge(int from, int to) {
//dfs
assert(!ord.empty() && ord[0] != -1);
assert(0 <= from && from < N);
assert(0 <= to && to < N);
if (ord[from] > ord[to]) swap(from, to);
if (ord[from] < lowlink[to]) return true;
else return false;
}
private:
int N;
vector<int> ord; //dfslowlink 使
vector<int> lowlink;
//
void initialize(int n) {
G.assign(n, vector<edge<T>>());
sp = -1;
dist.assign(n, INF);
prev.assign(n, -1);
prev_edge.assign(n, -1);
}
//使 dfs ()
bool dfs_closed(int v, int from, vector<int>& vec, vector<bool>& seen) {
vec.push_back(v);
if (seen.at(v)) return true;
else seen.at(v) = true;
for (auto&& ed : G.at(v)) {
int next_v = ed.to;
if (next_v == from) continue;
bool flag = dfs_closed(next_v, v, vec, seen);
if (flag) return true;
}
vec.pop_back();
return false;
}
//dfs使dfs ()
//res, edge_index dfs,
//first_ptr
void dfs_tree_func(int v, vector<pair<int, int>>& res, vector<int>& edge_index, vector<bool>& seen_v, vector<bool>& seen_e, int& first_ptr) {
seen_v[v] = true;
//
ord[v] = lowlink[v] = first_ptr++;
for (const auto& e : G[v]) {
seen_e[e.index] = true;
int nv = e.to;
if (!seen_v[nv]) {
res.push_back({ v, nv });
edge_index.push_back(e.index);
dfs_tree_func(nv, res, edge_index, seen_v, seen_e, first_ptr);
chmin(lowlink[v], lowlink[nv]);
}
else {
//v → nv 退 (backward edge)
if (!seen_e[e.index % 2 == 0 ? e.index + 1 : e.index - 1]) {
chmin(lowlink[v], ord[nv]);
}
}
}
}
};
//https://ei1333.github.io/algorithm/namori.html
//graph
template<typename T = long long>
class Namori : public graph<T> {
public:
Namori(int _n) : graph<T>(_n) {};
Namori() : graph<T>(0) {};
// ()
void decomposition(vector<int>& loop, vector<vector<int> >& forest) {
vector<int> cnt_from(this->G.size());
for (int i = 0; i < (int)this->G.size(); ++i) {
cnt_from[i] = this->G[i].size();
}
forest.resize(this->G.size());
queue<int> que;
vector<bool> seen((int)this->G.size(), false);
for (int i = 0; i < (int)this->G.size(); ++i) {
if (cnt_from[i] == 1) {
que.push(i);
seen[i] = true;
}
}
while (!que.empty()) {
int v = que.front(); que.pop();
for (auto&& ne : this->G[v]) {
int nv = ne.to;
if (seen[nv]) continue;
--cnt_from[nv];
forest[v].push_back(nv);
forest[nv].push_back(v);
if (cnt_from[nv] > 1) continue;
que.push(nv);
seen[nv] = true;
}
}
// seen true
for (int v = 0; v < (int)this->G.size(); ++v) {
if (seen[v]) continue;
seen[v] = true;
dfs_loop(v, seen);
break;
}
}
private:
void dfs_loop(int v, vector<bool>& seen) {
for (auto&& ne : this->G[v]) {
int nv = ne.to;
if (seen[nv]) continue;
seen[nv] = true;
dfs_loop(nv, seen);
}
};
};
signed main() {
int N; cin >> N;
Namori<int> G(N);
vector<int> a(N), b(N);
rep(i, N) {
cin >> a[i] >> b[i];
--a[i]; --b[i];
G.add_biedge(a[i], b[i]);
}
vector<int> loop;
vector<vector<int>> forest;
G.decomposition(loop, forest);
UnionFind uf(N);
rep(v, N) {
for (auto nv : forest[v]) {
uf.unite(v, nv);
}
}
vector<int> res;
rep(i, N) {
if (!uf.same(a[i], b[i])) res.push_back(i + 1);
}
cout << res.size() << endl;
print_vec(res);
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0