Submission #1204703

#TimeUsernameProblemLanguageResultExecution timeMemory
1204703RufatBridges (APIO19_bridges)C++20
13 / 100
3095 ms6096 KiB
/* ,----.. ____ ,----.. ,--, ,--, / / \ .--.--. ,----.. ,---,. ,---, ,---,. ,' , `.,-.----. ,---,. / / \ |'. \ / .`| / . : / / '. / / \ ,' .' | .' .' `\ ,' .' | ,-+-,.' _ |\ / \ ,--, ,' .' | / . : ; \ `\ /' / ; . / ;. \ : /`. / / . : ,---.' |,---.' \ ,---.' | ,-+-. ; , ||; : \ ,'_ /|,---.' | . / ;. \ `. \ / / .'. ; / ` ; | |--` . / ;. \ | | .'| | .`\ || | .' ,--.'|' | ;|| | .\ : .--. | | :| | .'. ; / ` ; \ \/ / ./ ; | ; \ ; | : ;_ . ; / ` ; : : |-,: : | ' |: : |-,| | ,', | ':. : |: | ,'_ /| : . |: : : ; | ; \ ; | \ \.' / | : | ; | '\ \ `. ; | ; \ ; | : | ;/|| ' ' ; :: | ;/|| | / | | ||| | \ : | ' | | . .: | |-,| : | ; | ' \ ; ; . | ' ' ' : `----. \| : | ; | ' | : .'' | ; . || : .'' | : | : |,| : . / | | ' | | || : ;/|. | ' ' ' : / \ \ \ ' ; \; / | __ \ \ |. | ' ' ' : | | |-,| | : | '| | |-,; . | ; |--' ; | | \ : | | : ' ;| | .'' ; \; / | ; /\ \ \ \ \ ', / / /`--' /' ; \; / | ' : ;/|' : | / ; ' : ;/|| : | | , | | ;\ \| ; ' | | '' : ' \ \ ', / ./__; \ ; \ ; : / '--'. / \ \ ', . \| | \| | '` ,/ | | \| : ' |/ : ' | \.': | : ; ; || | | ; : / | : / \ \ ; \ \ .' `--'---' ; : ; | : .'; : .' | : .'; | |`-' : : :-' ' : `--' \ : \ \ \ .' ; |/ \ ' | `---` \ \ .'`--"| | ,' | ,.' | | ,' | ;/ | |.' : , .-./ | ,' `---` `---' `--` `---` `----' '---' `----' '---' `---' `--`----' `----' */ //Author RufatM /*#pragma GCC optimize("Ofast") #pragma GCC target("avx,avx2,fma") #pragma GCC optimize("unroll-loops") #pragma GCC optimize("fast-math") #pragma GCC optimize("inline") #pragma GCC optimize("tree-vectorize") #pragma GCC optimize("loop-vectorize") #pragma GCC optimize("loop-interchange") #pragma GCC optimize("loop-block") #pragma GCC optimize("loop-strip-mine") #pragma GCC optimize("loop-optimize") #pragma GCC optimize("tree-loop-distribute-patterns") #pragma GCC optimize("tree-loop-distribute-force") #pragma GCC optimize("tree-loop-distribute") #pragma GCC optimize("tree-loop-vectorize") #pragma GCC optimize("tree-loop-ivcanon") #pragma GCC optimize("tree-loop-ivopts") */ #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #include <ext/pb_ds/detail/standard_policies.hpp> using namespace __gnu_pbds; using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef vector<int> vi; typedef vector<vector<int>> vvi; typedef vector<ll> vll; typedef vector<pii> vpii; typedef vector<vector<pii>> vvp; typedef vector<bool> vb; typedef vector<string> vs; #define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define endl '\n' #define pb push_back #define pf push_front #define eb emplace_back #define ff first #define ss second #define all(x) begin(x), end(x) #define rall(x) rbegin(x), rend(x) #define mt19937_64 mt_rand(chrono::steady_clock::now().time_since_epoch().count()) template<typename T> using min_heap = priority_queue<T, vector<T>, greater<T>>; template<typename T> using max_heap = priority_queue<T>; typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset; template<typename T> bool isPrime(T n) { if (n <= 1)return false;if (n <= 3)return true;if (n % 2 == 0 || n % 3 == 0)return false;for (T i = 5;i * i <= n;i += 6)if (n % i == 0 || n % (i + 2) == 0)return false;return true; } const int MOD = 998244353; const int INF = 1e9 + 7; const int LOG = 21; const long long LINF = 1e18 + 7; const int MAXN = 1e5 + 7; const int MAXM = 1e6 + 7; ll binpow(ll a, ll b, ll m = MOD) { ll res = 1; a %= m; while (b > 0) { if (b & 1) res = res * a % m; a = a * a % m; b >>= 1; } return res; } ll modinv(ll a, ll m = MOD) { return binpow(a, m - 2, m); } struct segment_tree { int n; vector<ll> t; segment_tree(int _n) : n(_n) { t.assign(4 * n, 0); } void build(int v, int tl, int tr, const vector<ll>& a) { if (tl == tr) { t[v] = a[tl]; } else { int tm = (tl + tr) / 2; build(v * 2, tl, tm, a); build(v * 2 + 1, tm + 1, tr, a); t[v] = t[v * 2] + t[v * 2 + 1]; } } void update(int v, int tl, int tr, int pos, ll new_val) { if (tl == tr) { t[v] = new_val; } else { int tm = (tl + tr) / 2; if (pos <= tm) update(v * 2, tl, tm, pos, new_val); else update(v * 2 + 1, tm + 1, tr, pos, new_val); t[v] = t[v * 2] + t[v * 2 + 1]; } } ll query(int v, int tl, int tr, int l, int r) { if (l > r) return 0; if (l == tl && r == tr) return t[v]; int tm = (tl + tr) / 2; return query(v * 2, tl, tm, l, min(r, tm)) + query(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r); } }; struct DSU { vi parent, size; DSU(int n) { parent.resize(n); iota(all(parent), 0); size.assign(n, 1); } int find(int v) { return v == parent[v] ? v : parent[v] = find(parent[v]); } bool unite(int a, int b) { a = find(a), b = find(b); if (a == b) return false; if (size[a] < size[b]) swap(a, b); parent[b] = a; size[a] += size[b]; return true; } }; struct Fenwick { vi bit; int n; Fenwick(int _n) : n(_n) { bit.assign(n + 1, 0); } void add(int idx, int val) { for (; idx <= n; idx += idx & -idx) bit[idx] += val; } int sum(int idx) { int res = 0; for (; idx > 0; idx -= idx & -idx) res += bit[idx]; return res; } int range_sum(int l, int r) { return sum(r) - sum(l - 1); } }; const int dx[4] = {-1, 0, 1, 0}; const int dy[4] = {0, 1, 0, -1}; template<typename T> void read(T &x) { x = 0; char c = getchar(); bool neg = false; while (c < '0' || c > '9') { if (c == '-') neg = true; c = getchar(); } while (c >= '0' && c <= '9') { x = x * 10 + (c - '0'); c = getchar(); } if (neg) x = -x; } template<typename T> void write(T x) { if (x < 0) putchar('-'), x = -x; char buf[20]; int i = 0; do { buf[i++] = x % 10 + '0'; x /= 10; } while (i); while (i--) putchar(buf[i]); putchar('\n'); } void bigwrite(ll x) { if (x < 0) putchar('-'), x = -x; char buf[20]; int i = 0; do { buf[i++] = x % 10 + '0'; x /= 10; } while (i); while (i--) putchar(buf[i]); putchar('\n'); } struct bignum { static const int base = 1000000000, base_digits = 9; vector<int> digits; bool sign; bignum() : sign(1) {} bignum(long long v) { *this = v; } bignum(const string &s) { read(s); } void operator=(const bignum &v) { sign = v.sign; digits = v.digits; } bignum& operator=(long long v) { sign = v >= 0; v = std::abs(v); digits.clear(); while (v) { digits.push_back(v % base); v /= base; } return *this; } bignum& operator=(const string &s) { read(s); return *this; } void trim() { while (!digits.empty() && digits.back() == 0) digits.pop_back(); if (digits.empty()) sign = 1; } void read(const string &s) { sign = 1; digits.clear(); int pos = 0; while (pos < s.size() && (s[pos] == '-' || s[pos] == '+')) { if (s[pos] == '-') sign = 0; ++pos; } for (int i = s.size() - 1; i >= pos; i -= base_digits) { int x = 0; for (int j = std::max(pos, i - base_digits + 1); j <= i; j++) x = x * 10 + (s[j] - '0'); digits.push_back(x); } trim(); } string to_string() const { if (digits.empty()) return "0"; string res = sign ? "" : "-"; res += std::to_string(digits.back()); for (int i = int(digits.size()) - 2; i >= 0; --i) res += std::string(base_digits - std::to_string(digits[i]).size(), '0') + std::to_string(digits[i]); return res; } friend ostream& operator<<(ostream &stream, const bignum &v) { return stream << v.to_string(); } friend istream& operator>>(istream &stream, bignum &v) { string s; stream >> s; v.read(s); return stream; } void print128(__int128 x) const { if (x == 0) { cout << 0; return; } if (x < 0) { cout << '-'; x = -x; } char buf[50]; int p = 0; while (x) { buf[p++] = '0' + (x % 10); x /= 10; } for (int i = p - 1; i >= 0; --i) cout << buf[i]; } bool is_zero() const { return digits.empty(); } int compare(const bignum &v) const { if (sign != v.sign) return sign ? 1 : -1; if (digits.size() != v.digits.size()) return (digits.size() > v.digits.size() ? 1 : -1) * (sign ? 1 : -1); for (int i = int(digits.size()) - 1; i >= 0; --i) if (digits[i] != v.digits[i]) return (digits[i] > v.digits[i] ? 1 : -1) * (sign ? 1 : -1); return 0; } bool operator<(const bignum &v) const { return compare(v) < 0; } bool operator>(const bignum &v) const { return compare(v) > 0; } bool operator<=(const bignum &v) const { return compare(v) <= 0; } bool operator>=(const bignum &v) const { return compare(v) >= 0; } bool operator==(const bignum &v) const { return compare(v) == 0; } bool operator!=(const bignum &v) const { return compare(v) != 0; } bignum abs() const { bignum res = *this; res.sign = 1; return res; } int size() const { return digits.size(); } int digit_sum() const { int s = 0; for (auto d : digits) { int x = d; while (x) { s += x % 10; x /= 10; } } return s; } int digits_count() const { if (is_zero()) return 1; int cnt = (digits.size() - 1) * base_digits; int top = digits.back(); while (top) { ++cnt; top /= 10; } return cnt; } int parity() const { return is_zero() ? 0 : digits[0] % 2; } void shift_left(int n) { if (is_zero() || n == 0) return; digits.insert(digits.begin(), n, 0); } void shift_right(int n) { if (n >= digits.size()) digits.clear(); else digits.erase(digits.begin(), digits.begin() + n); trim(); } bignum operator-() const { bignum res = *this; if (!is_zero()) res.sign = !sign; return res; } bignum& operator+=(const bignum &v) { *this = *this + v; return *this; } bignum& operator-=(const bignum &v) { *this = *this - v; return *this; } bignum& operator*=(const bignum &v) { *this = *this * v; return *this; } bignum& operator/=(const bignum &v) { *this = *this / v; return *this; } bignum& operator%=(const bignum &v) { *this = *this % v; return *this; } bignum operator+(const bignum &v) const { if (!sign && !v.sign) return -((-*this) + (-v)); if (!sign) return v - (-*this); if (!v.sign) return *this - (-v); bignum res; int carry = 0; for (int i = 0; i < std::max(size(), v.size()) || carry; ++i) { int x = carry; if (i < size()) x += digits[i]; if (i < v.size()) x += v.digits[i]; res.digits.push_back(x % base); carry = x / base; } res.trim(); return res; } bignum operator-(const bignum &v) const { if (!v.sign) return *this + (-v); if (!sign) return -((-*this) + v); if (*this < v) return -(v - *this); bignum res = *this; int carry = 0; for (int i = 0; i < v.size() || carry; ++i) { res.digits[i] -= carry + (i < v.size() ? v.digits[i] : 0); if (res.digits[i] < 0) { res.digits[i] += base; carry = 1; } else carry = 0; } res.trim(); return res; } bignum operator*(long long v) const { bignum res; res.sign = (v >= 0) == sign; v = std::abs(v); __int128 carry = 0; for (int i = 0; i < size() || carry; ++i) { __int128 cur = carry; if (i < size()) cur += (__int128)digits[i] * v; res.digits.push_back(int(cur % base)); carry = cur / base; } res.trim(); return res; } bignum operator*(const bignum &v) const { bignum res; res.sign = (sign == v.sign); res.digits.assign(size() + v.size(), 0); for (int i = 0; i < size(); ++i) { __int128 carry = 0; for (int j = 0; j < v.size() || carry; ++j) { __int128 cur = res.digits[i + j] + (__int128)digits[i] * (j < v.size() ? v.digits[j] : 0) + carry; res.digits[i + j] = int(cur % base); carry = cur / base; } } res.trim(); return res; } bignum operator/(long long v) const { bignum res = *this; res.sign = (v >= 0) == sign; v = std::abs(v); __int128 rem = 0; for (int i = int(res.size()) - 1; i >= 0; --i) { __int128 cur = res.digits[i] + rem * base; res.digits[i] = int(cur / v); rem = cur % v; } res.trim(); return res; } pair<bignum, long long> divmod(long long v) const { bignum res = *this; res.sign = (v >= 0) == sign; v = std::abs(v); __int128 rem = 0; for (int i = int(res.size()) - 1; i >= 0; --i) { __int128 cur = res.digits[i] + rem * base; res.digits[i] = int(cur / v); rem = cur % v; } res.trim(); return {res, (long long)(sign ? rem : -rem)}; } bignum operator/(const bignum &v) const { return divmod_bignum(v).first; } bignum operator%(const bignum &v) const { return divmod_bignum(v).second; } pair<bignum, bignum> divmod_bignum(const bignum &v) const { int norm = base / (v.digits.back() + 1); bignum a = abs() * norm; bignum b = v.abs() * norm; bignum q, r; q.digits.resize(a.size()); for (int i = int(a.size()) - 1; i >= 0; --i) { r.shift_left(1); r.digits[0] = a.digits[i]; r.trim(); int s1 = r.size() <= b.size() ? 0 : r.digits[b.size()]; int s2 = r.size() <= b.size() - 1 ? 0 : r.digits[b.size() - 1]; long long d = ((long long)base * s1 + s2) / b.digits.back(); r = r - b * d; while (r < 0) { r = r + b; --d; } q.digits[i] = d; } q.trim(); r = r / norm; if (!sign) q = -q; if (!sign) r = -r; return {q, r}; } bignum pow(long long n) const { bignum a = *this, res = 1; while (n > 0) { if (n & 1) res = res * a; a = a * a; n >>= 1; } return res; } bignum sqrt() const { bignum left = 0, right = *this, ans = 0; while (left <= right) { bignum mid = (left + right) / 2; if (mid * mid <= *this) { ans = mid; left = mid + 1; } else right = mid - 1; } return ans; } bignum gcd(const bignum &v) const { return v.is_zero() ? *this : v.gcd(*this % v); } bignum lcm(const bignum &v) const { return (*this / gcd(v)) * v; } bignum abs_mod(long long v) const { __int128 rem = 0; for (int i = int(size()) - 1; i >= 0; --i) rem = (rem * base + digits[i]) % v; return rem; } void inc() { *this += 1; } void dec() { *this -= 1; } bignum max(const bignum &v) const { return (*this < v) ? v : *this; } bignum min(const bignum &v) const { return (*this < v) ? *this : v; } bignum next() const { bignum res = *this; res.inc(); return res; } bignum prev() const { bignum res = *this; res.dec(); return res; } vector<int> as_vector() const { return digits; } int leading_digit() const { return is_zero() ? 0 : std::to_string(digits.back())[0] - '0'; } int trailing_digit() const { return is_zero() ? 0 : digits[0] % 10; } bignum powmod(long long n, long long mod) const { bignum a = *this % mod, res = 1; while (n > 0) { if (n & 1) res = (res * a) % mod; a = (a * a) % mod; n >>= 1; } return res; } bool is_even() const { return is_zero() ? true : (digits[0] % 2 == 0); } bool is_odd() const { return !is_even(); } bignum factorial() const { bignum res = 1; for (bignum i = 2; i <= *this; i += 1) res *= i; return res; } bignum binomial(const bignum &k) const { bignum res = 1, x = *this, y = k; for (bignum i = 1; i <= k; i += 1) { res = res * (x - i + 1) / i; } return res; } bignum reverse_digits() const { string s = to_string(); std::reverse(s.begin() + (sign ? 0 : 1), s.end()); return bignum(s); } int digit_at(int idx) const { string s = to_string(); if (idx < 0 || idx >= s.size()) return 0; return s[s.size() - 1 - idx] - '0'; } bignum operator++() { *this += 1; return *this; } bignum operator--() { *this -= 1; return *this; } }; struct rabinkarp { typedef long long ll; static const ll mod1 = 1000000007; static const ll mod2 = 1000000009; static const ll base1 = 911; static const ll base2 = 3571; vector<ll> pow1, pow2, hash1, hash2; string s; rabinkarp(const string &_s) { s = _s; int n = s.size(); pow1.resize(n+1), pow2.resize(n+1), hash1.resize(n+1), hash2.resize(n+1); pow1[0] = pow2[0] = 1; for(int i=1;i<=n;++i) { pow1[i] = (pow1[i-1]*base1)%mod1; pow2[i] = (pow2[i-1]*base2)%mod2; } hash1[0] = hash2[0] = 0; for(int i=0;i<n;++i) { hash1[i+1] = (hash1[i]*base1 + s[i]) % mod1; hash2[i+1] = (hash2[i]*base2 + s[i]) % mod2; } } pair<ll,ll> get_hash(int l, int r) { ll h1 = (hash1[r] - hash1[l]*pow1[r-l]%mod1 + mod1)%mod1; ll h2 = (hash2[r] - hash2[l]*pow2[r-l]%mod2 + mod2)%mod2; return {h1, h2}; } vector<int> find_occurrences(const string &pat) { int n = s.size(), m = pat.size(); rabinkarp pat_hash(pat); pair<ll,ll> hpat = pat_hash.get_hash(0, m); vector<int> occ; for(int i=0;i+m<=n;++i) if(get_hash(i,i+m)==hpat) occ.push_back(i); return occ; } }; struct fft { typedef complex<double> cd; vector<cd> roots; vector<int> rev; void ensure_base(int nbase) { int sz = 1 << nbase; if((int)roots.size() >= sz) return; roots.resize(sz); rev.resize(sz); for(int i=0;i<sz;++i) { double angle = 2 * acos(-1) * i / sz; roots[i] = cd(cos(angle), sin(angle)); } } void fft_rec(vector<cd> &a, int n, bool invert) { int N = a.size(); int L = 0; while((1 << L) < N) ++L; rev.resize(N); for(int i=0;i<N;++i) { rev[i] = 0; for(int j=0;j<L;++j) if(i & (1 << j)) rev[i] |= 1 << (L-1-j); } for(int i=0;i<N;++i) if(i < rev[i]) swap(a[i], a[rev[i]]); for(int len=2; len<=N; len<<=1) { int half = len>>1; int diff = (int)roots.size()/len; for(int i=0;i<N;i+=len) for(int j=0,k=0;j<half;++j,k+=diff) { cd u = a[i+j]; cd v = a[i+j+half]*roots[k]; a[i+j] = u+v; a[i+j+half] = u-v; } } if(invert) { for(int i=0;i<N;++i) a[i]/=N; reverse(a.begin()+1, a.end()); } } vector<int> multiply(const vector<int>& a, const vector<int>& b) { int need = a.size() + b.size() - 1; int nbase = 0; while((1<<nbase) < need) ++nbase; ensure_base(nbase); int sz = 1 << nbase; vector<cd> fa(sz), fb(sz); for(int i=0;i<(int)a.size();++i) fa[i]=a[i]; for(int i=0;i<(int)b.size();++i) fb[i]=b[i]; fft_rec(fa, sz, false); fft_rec(fb, sz, false); for(int i=0;i<sz;++i) fa[i]*=fb[i]; fft_rec(fa, sz, true); vector<int> res(need); for(int i=0;i<need;++i) res[i] = int64_t(fa[i].real() + 0.5); return res; } vector<int> multiply_str(const string& s, const string& t) { vector<int> a, b; for(int i=s.size()-1;i>=0;--i) a.push_back(s[i]-'0'); for(int i=t.size()-1;i>=0;--i) b.push_back(t[i]-'0'); vector<int> res = multiply(a, b); for(int i=0;i+1<res.size();++i) { if(res[i]>=10) { if(i+1==res.size()) res.push_back(0); res[i+1] += res[i]/10; res[i] %= 10; } } return res; } }; struct trie { static const int ALPHABET = 26; struct node { int cnt; node *children[ALPHABET]; node() : cnt(0) { memset(children, 0, sizeof(children)); } }; node *root; trie() { root = new node(); } void insert(const string &s) { node *cur = root; for (char c : s) { int idx = c - 'a'; if (!cur->children[idx]) cur->children[idx] = new node(); cur = cur->children[idx]; cur->cnt++; } } bool search(const string &s) { node *cur = root; for (char c : s) { int idx = c - 'a'; if (!cur->children[idx]) return false; cur = cur->children[idx]; } return true; } int prefix_count(const string &s) { node *cur = root; for (char c : s) { int idx = c - 'a'; if (!cur->children[idx]) return 0; cur = cur->children[idx]; } return cur->cnt; } void erase(const string &s) { erase(root, s, 0); } bool erase(node *cur, const string &s, int d) { if (d == s.size()) return true; int idx = s[d] - 'a'; if (!cur->children[idx]) return false; if (erase(cur->children[idx], s, d+1)) { cur->children[idx]->cnt--; if (cur->children[idx]->cnt == 0) { delete cur->children[idx]; cur->children[idx] = nullptr; } } return false; } }; struct hashtable { static const int CAP = 200003; vector<pair<int, int>> table; vector<bool> used; hashtable() : table(CAP, {-1, -1}), used(CAP, false) {} int hash(int key) const { return ((key % CAP) + CAP) % CAP; } void insert(int key, int value) { int idx = hash(key); while (used[idx] && table[idx].first != key) { idx = (idx + 1) % CAP; } table[idx] = {key, value}; used[idx] = true; } bool contains(int key) const { int idx = hash(key); int start = idx; while (used[idx]) { if (table[idx].first == key) return true; idx = (idx + 1) % CAP; if (idx == start) break; } return false; } int get(int key) const { int idx = hash(key); int start = idx; while (used[idx]) { if (table[idx].first == key) return table[idx].second; idx = (idx + 1) % CAP; if (idx == start) break; } return -1; } void erase(int key) { int idx = hash(key); int start = idx; while (used[idx]) { if (table[idx].first == key) { used[idx] = false; table[idx] = {-1, -1}; return; } idx = (idx + 1) % CAP; if (idx == start) break; } } void clear() { fill(table.begin(), table.end(), make_pair(-1, -1)); fill(used.begin(), used.end(), false); } int size() const { int cnt = 0; for (int i = 0; i < CAP; ++i) if (used[i]) cnt++; return cnt; } }; struct redblacktree { enum Color { RED, BLACK }; struct Node { int key, count, subtree_size; Color color; Node *left, *right, *parent; Node(int k) : key(k), count(1), subtree_size(1), color(RED), left(nullptr), right(nullptr), parent(nullptr) {} }; Node* root; redblacktree() : root(nullptr) {} void update(Node* x) { if (!x) return; x->subtree_size = x->count; if (x->left) x->subtree_size += x->left->subtree_size; if (x->right) x->subtree_size += x->right->subtree_size; } void left_rotate(Node* x) { Node* y = x->right; x->right = y->left; if (y->left) y->left->parent = x; y->parent = x->parent; if (!x->parent) root = y; else if (x == x->parent->left) x->parent->left = y; else x->parent->right = y; y->left = x; x->parent = y; update(x); update(y); } void right_rotate(Node* y) { Node* x = y->left; y->left = x->right; if (x->right) x->right->parent = y; x->parent = y->parent; if (!y->parent) root = x; else if (y == y->parent->left) y->parent->left = x; else y->parent->right = x; x->right = y; y->parent = x; update(y); update(x); } void insert(int key) { Node* z = root; Node* p = nullptr; while (z) { p = z; z->subtree_size++; if (key == z->key) { z->count++; return; } else if (key < z->key) z = z->left; else z = z->right; } Node* n = new Node(key); n->parent = p; if (!p) root = n; else if (key < p->key) p->left = n; else p->right = n; insert_fix(n); } void insert_fix(Node* z) { while (z->parent && z->parent->color == RED) { if (z->parent == z->parent->parent->left) { Node* y = z->parent->parent->right; if (y && y->color == RED) { z->parent->color = BLACK; y->color = BLACK; z->parent->parent->color = RED; z = z->parent->parent; } else { if (z == z->parent->right) { z = z->parent; left_rotate(z); } z->parent->color = BLACK; z->parent->parent->color = RED; right_rotate(z->parent->parent); } } else { Node* y = z->parent->parent->left; if (y && y->color == RED) { z->parent->color = BLACK; y->color = BLACK; z->parent->parent->color = RED; z = z->parent->parent; } else { if (z == z->parent->left) { z = z->parent; right_rotate(z); } z->parent->color = BLACK; z->parent->parent->color = RED; left_rotate(z->parent->parent); } } } root->color = BLACK; } Node* find(int key) const { Node* x = root; while (x) { if (key == x->key) return x; else if (key < x->key) x = x->left; else x = x->right; } return nullptr; } void erase(int key) { Node* z = find(key); if (!z) return; if (z->count > 1) { z->count--; erase_update_up(z); return; } erase_update_up(z); Node* y = z; Color y_original = y->color; Node* x; if (!z->left) { x = z->right; transplant(z, z->right); } else if (!z->right) { x = z->left; transplant(z, z->left); } else { y = minimum(z->right); y_original = y->color; x = y->right; if (y->parent == z) { if (x) x->parent = y; } else { transplant(y, y->right); y->right = z->right; if (y->right) y->right->parent = y; } transplant(z, y); y->left = z->left; if (y->left) y->left->parent = y; y->color = z->color; update(y); } if (y_original == BLACK) erase_fix(x, z->parent); delete z; } void erase_update_up(Node* z) { while (z) { update(z); z = z->parent; } } void erase_fix(Node* x, Node* p) { while ((x != root) && (!x || x->color == BLACK)) { if (x == (p ? p->left : nullptr)) { Node* w = (p ? p->right : nullptr); if (w && w->color == RED) { w->color = BLACK; p->color = RED; left_rotate(p); w = (p ? p->right : nullptr); } if ((!w || ((!(w->left) || w->left->color == BLACK) && (!(w->right) || w->right->color == BLACK)))) { if (w) w->color = RED; x = p; if (x) p = x->parent; } else { if (!(w->right) || w->right->color == BLACK) { if (w && w->left) w->left->color = BLACK; if (w) w->color = RED; right_rotate(w); w = (p ? p->right : nullptr); } if (w) w->color = p->color; if (p) p->color = BLACK; if (w && w->right) w->right->color = BLACK; left_rotate(p); x = root; break; } } else { Node* w = (p ? p->left : nullptr); if (w && w->color == RED) { w->color = BLACK; p->color = RED; right_rotate(p); w = (p ? p->left : nullptr); } if ((!w || ((!(w->left) || w->left->color == BLACK) && (!(w->right) || w->right->color == BLACK)))) { if (w) w->color = RED; x = p; if (x) p = x->parent; } else { if (!(w->left) || w->left->color == BLACK) { if (w && w->right) w->right->color = BLACK; if (w) w->color = RED; left_rotate(w); w = (p ? p->left : nullptr); } if (w) w->color = p->color; if (p) p->color = BLACK; if (w && w->left) w->left->color = BLACK; right_rotate(p); x = root; break; } } } if (x) x->color = BLACK; } void transplant(Node* u, Node* v) { if (!u->parent) root = v; else if (u == u->parent->left) u->parent->left = v; else u->parent->right = v; if (v) v->parent = u->parent; if (v) update(v); if (u->parent) update(u->parent); } Node* minimum(Node* x) const { while (x && x->left) x = x->left; return x; } Node* maximum(Node* x) const { while (x && x->right) x = x->right; return x; } Node* lower_bound(int key) const { Node* x = root; Node* res = nullptr; while (x) { if (x->key >= key) { res = x; x = x->left; } else x = x->right; } return res; } Node* upper_bound(int key) const { Node* x = root; Node* res = nullptr; while (x) { if (x->key > key) { res = x; x = x->left; } else x = x->right; } return res; } Node* predecessor(Node* x) const { if (x->left) return maximum(x->left); Node* y = x->parent; while (y && x == y->left) { x = y; y = y->parent; } return y; } Node* successor(Node* x) const { if (x->right) return minimum(x->right); Node* y = x->parent; while (y && x == y->right) { x = y; y = y->parent; } return y; } int next(int key) const { Node* n = find(key); Node* s = successor(n); return s ? s->key : INT_MAX; } int prev(int key) const { Node* n = find(key); Node* p = predecessor(n); return p ? p->key : INT_MIN; } int count(int key) const { Node* n = find(key); return n ? n->count : 0; } int size() const { return root ? root->subtree_size : 0; } int rank(int key) const { Node* x = root; int r = 0; while (x) { if (key < x->key) x = x->left; else { int left_size = x->left ? x->left->subtree_size : 0; r += left_size + x->count * (x->key <= key); x = x->right; } } return r; } int select(int k) const { Node* x = root; while (x) { int left_size = x->left ? x->left->subtree_size : 0; if (k <= left_size) x = x->left; else if (k > left_size + x->count) { k -= left_size + x->count; x = x->right; } else return x->key; } return INT_MIN; } void inorder() const { inorder(root); cout << endl; } void inorder(Node* x) const { if (!x) return; inorder(x->left); for (int i = 0; i < x->count; i++) cout << x->key << " "; inorder(x->right); } void print_tree(Node* n, int depth = 0) const { if (!n) return; print_tree(n->right, depth + 1); for (int i = 0; i < depth; ++i) cout << " "; cout << n->key << (n->color == RED ? "R" : "B") << " (" << n->subtree_size << ")\n"; print_tree(n->left, depth + 1); } void print() const { print_tree(root); } void clear() { clear(root); root = nullptr; } void clear(Node* x) { if (!x) return; clear(x->left); clear(x->right); delete x; } int range_count(int l, int r) const { return rank(r) - rank(l - 1); } bool is_bst(Node* n, int mn, int mx) const { if (!n) return true; if (n->key < mn || n->key > mx) return false; return is_bst(n->left, mn, n->key - 1) && is_bst(n->right, n->key + 1, mx); } bool is_bst() const { return is_bst(root, INT_MIN, INT_MAX); } int height(Node* n = nullptr) const { if (!n) n = root; if (!n) return 0; return 1 + max(height(n->left), height(n->right)); } }; struct llint { long long x; llint(long long v = 0) : x(v) {} operator long long() const { return x; } llint& operator=(long long v) { x = v; return *this; } llint operator+(const llint& b) const { return x + b.x; } llint operator-(const llint& b) const { return x - b.x; } llint operator*(const llint& b) const { return x * b.x; } llint operator/(const llint& b) const { return x / b.x; } llint operator%(const llint& b) const { return x % b.x; } llint& operator+=(const llint& b) { x += b.x; return *this; } llint& operator-=(const llint& b) { x -= b.x; return *this; } llint& operator*=(const llint& b) { x *= b.x; return *this; } llint& operator/=(const llint& b) { x /= b.x; return *this; } llint& operator%=(const llint& b) { x %= b.x; return *this; } llint operator-() const { return -x; } llint operator++(int) { llint tmp = *this; ++x; return tmp; } llint operator--(int) { llint tmp = *this; --x; return tmp; } llint& operator++() { ++x; return *this; } llint& operator--() { --x; return *this; } bool operator==(const llint& b) const { return x == b.x; } bool operator!=(const llint& b) const { return x != b.x; } bool operator<(const llint& b) const { return x < b.x; } bool operator>(const llint& b) const { return x > b.x; } bool operator<=(const llint& b) const { return x <= b.x; } bool operator>=(const llint& b) const { return x >= b.x; } friend ostream& operator<<(ostream& os, const llint& v) { return os << v.x; } llint abs() const { return x < 0 ? -x : x; } llint pow(llint k) const { llint res = 1, a = x; while (k.x) { if (k.x & 1) res *= a; a *= a; k.x >>= 1; } return res; } llint gcd(const llint& b) const { return b.x ? llint(__gcd(x, b.x)) : *this; } llint lcm(const llint& b) const { return x / gcd(b).x * b.x; } void swap(llint& b) { std::swap(x, b.x); } }; inline istream& operator>>(istream& is, llint& v) { is >> v.x; return is; } template<typename T> bool chmin(T &a, const T &b) { return (b < a) ? (a = b, true) : false; } template<typename T> bool chmax(T &a, const T &b) { return (b > a) ? (a = b, true) : false; } int divceil(int a, int b) { return a / b + (a % b != 0); } int pct(int x) { return __builtin_popcount(x); } int bits(int x) { return x == 0 ? -1 : 31 - __builtin_clz(x); } template<class Fun> class y_combinator_result { Fun fun_; public: template<class T> explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {} template<class ...Args> decltype(auto) operator()(Args &&...args) { return fun_(std::ref(*this), std::forward<Args>(args)...); } }; template<class Fun> decltype(auto) y_combinator(Fun &&fun) { return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun)); } struct custom_hash { static uint64_t splitmix64(uint64_t x) { x += 0x9e3779b97f4a7c15; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return x ^ (x >> 31); } size_t operator()(pll x) const { static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count(); return splitmix64(x.first ^ (x.second << 1)) + FIXED_RANDOM; } }; template<typename T> struct sparse_table { vector<vector<T>> st; vector<int> log; T (*merge)(T, T); sparse_table(const vector<T>& v, T (*f)(T, T)) : merge(f) { int n = v.size(); int K = 32 - __builtin_clz(n); st.assign(K, vector<T>(n)); log.assign(n + 1, 0); for (int i = 2; i <= n; i++) log[i] = log[i / 2] + 1; st[0] = v; for (int j = 1; j < K; j++) for (int i = 0; i + (1 << j) <= n; i++) st[j][i] = merge(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]); } T query(int l, int r) { int j = log[r - l + 1]; return merge(st[j][l], st[j][r - (1 << j) + 1]); } }; struct Edge{ int u, v, w; }; signed main(){ fastio; int t = 1; //cin >> t; while(t--){ int n, m; cin >> n >> m; vector<Edge> edges(m + 1); vector<vpii> g(n + 1); for (int i = 1; i <= m; i++){ int u, v, w; cin >> u >> v >> w; edges[i] = {u, v, w}; g[u].pb({v, i}); g[v].pb({u, i}); } int q; cin >> q; while(q--){ int type; cin >> type; if(type == 1){ int b, r; cin >> b >> r; edges[b].w = r; } else{ int s, w; cin >> s >> w; vb vis(n + 1, false); queue<int> qu; vis[s] = true; qu.push(s); int cnt = 0; while(!qu.empty()){ int u = qu.front(); qu.pop(); cnt++; for(auto &p : g[u]){ int v = p.ff; int id = p.ss; if(!vis[v] and edges[id].w >= w){ vis[v] = true; qu.push(v); } } } cout << cnt << "\n"; } } } }

Compilation message (stderr)

bridges.cpp: In function 'void bigwrite(ll)':
bridges.cpp:185:15: warning: iteration 2147483647 invokes undefined behavior [-Waggressive-loop-optimizations]
  185 |     do { buf[i++] = x % 10 + '0'; x /= 10; } while (i);
      |              ~^~
bridges.cpp:185:53: note: within this loop
  185 |     do { buf[i++] = x % 10 + '0'; x /= 10; } while (i);
      |                                                     ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...