#include <bits/stdc++.h>
// #include <tr2/dynamic_bitset>
using namespace std;
// using namespace tr2;
#pragma GCC optimize("O3,unroll-loops,Ofast")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
const long double eps = 1e-9;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int randgen(int left, int right) {
return uniform_int_distribution<int>(left, right)(rng);
}
long long randgenll(long long left, long long right) {
return uniform_int_distribution<long long>(left, right)(rng);
}
typedef long long ll;
typedef long double ld;
const int mod = 1e9 + 7;
struct Mint
{
int val;
Mint(int x = 0)
{
val = x % mod;
}
Mint(long long x)
{
val = x % mod;
}
Mint operator+(Mint oth)
{
return val + oth.val;
}
Mint operator*(Mint oth)
{
return 1LL * val * oth.val;
}
Mint operator-(Mint oth)
{
return val - oth.val + mod;
}
Mint fp(Mint a, long long n){
Mint p = 1;
while(n){
if(n & 1){
p = p * a;
}
a = a * a;
n /= 2;
}
return p;
}
Mint operator/(Mint oth){
Mint invers = fp(oth, mod - 2);
return 1LL * val * invers.val;
}
friend ostream& operator << (ostream& os, const Mint& lol){
os << lol.val;
return os;
}
};
struct AINT{
vector<pair<ll,Mint>> aint;
vector<pair<ll,Mint>> lazy;
pair<ll,Mint> b;
AINT(int n){
b = {1e18,Mint(0)};
aint.assign(n * 4 + 1,make_pair(1e18,Mint(0)));
lazy.assign(n * 4 + 1, make_pair(1e18, Mint(0)));
}
void update(int v, int tl, int tr, int l, int r, pair<ll,Mint> val){
if(lazy[v].first != 1e18){
if(aint[v].first == lazy[v].first){
aint[v].second = aint[v].second + lazy[v].second;
}else if(aint[v].first > lazy[v].first) aint[v] = lazy[v];
if(tl != tr){
if(lazy[v * 2].first == lazy[v].first){
lazy[v * 2].second = lazy[v * 2].second + lazy[v].second;
}else if(lazy[v * 2].first > lazy[v].first) lazy[v * 2] = lazy[v];
if(lazy[v * 2 + 1].first == lazy[v].first){
lazy[v * 2 + 1].second = lazy[v * 2 + 1].second + lazy[v].second;
}else if(lazy[v * 2 + 1].first > lazy[v].first){
lazy[v * 2 + 1] = lazy[v];
}
}
lazy[v] = b;
}
if(l <= tl && r >= tr){
if(aint[v].first == val.first){
aint[v].second = aint[v].second + val.second;
}else if(aint[v].first > val.first){
aint[v] = val;
}
if(tl != tr){
if(lazy[v * 2].first == val.first){
lazy[v * 2].second = lazy[v * 2].second + val.second;
}else if(lazy[v * 2].first > val.first){
lazy[v * 2] = val;
}
if(lazy[v * 2 + 1].first == val.first){
lazy[v * 2 + 1].second = lazy[v * 2 + 1].second + val.second;
}else if(lazy[v * 2 + 1].first > val.first){
lazy[v * 2 + 1] = val;
}
}
return;
}
if(l > tr || r < tl) return;
int tm = (tl + tr) / 2;
update(v * 2, tl, tm, l,r , val);
update(v * 2 + 1, tm + 1, tr, l, r, val);
if(aint[v * 2].first == aint[v * 2 + 1].first){
aint[v] = aint[v * 2];
aint[v].second = aint[v].second + aint[v * 2 + 1].second;
}else{
if(aint[v * 2].first < aint[v * 2 + 1].first) aint[v] = aint[v * 2];
else aint[v] = aint[v * 2 + 1];
}
}
pair<ll,Mint> query(int v, int tl, int tr, int l, int r){
if(lazy[v].first != 1e18){
if(aint[v].first == lazy[v].first){
aint[v].second = aint[v].second + lazy[v].second;
}else if(aint[v].first > lazy[v].first) aint[v] = lazy[v];
if(tl != tr){
if(lazy[v * 2].first == lazy[v].first){
lazy[v * 2].second = lazy[v * 2].second + lazy[v].second;
}else if(lazy[v * 2].first > lazy[v].first) lazy[v * 2] = lazy[v];
if(lazy[v * 2 + 1].first == lazy[v].first){
lazy[v * 2 + 1].second = lazy[v * 2 + 1].second + lazy[v].second;
}else if(lazy[v * 2 + 1].first > lazy[v].first){
lazy[v * 2 + 1] = lazy[v];
}
}
lazy[v] = b;
}
if(l <= tl && r >= tr) return aint[v];
if(l > tr || r < tl) return make_pair(1e18,Mint(0));
int tm = (tl + tr) / 2;
pair<ll,Mint> p1 = query(v * 2, tl ,tm, l, r);
pair<ll,Mint> p2 = query(v * 2 + 1, tm + 1, tr, l,r);
if(p1.first == p2.first){
p1.second = p1.second + p2.second;
return p1;
}else if(p1.first < p2.first) return p1;
return p2;
// int tm = (tl + tr) / 2;
// if(l <= tl && r >= tr) return aint[v];
// if(l > tr || r < tl) return 0;
// return max(query(v * 2, tl, tm,l,r), query(v * 2 + 1, tm + 1, tr, l,r));
}
};
struct AIB{
vector<int> aib;
AIB(int n){
aib.assign(n + 1,0);
}
void update(int pos, int val){
for(; pos < aib.size(); pos += (pos & -pos)){
aib[pos] += val;
}
}
int query(int pos){
int pl = 0;
for(; pos > 0; pos -= (pos & -pos)) pl += aib[pos];
return pl;
}
};
int red = 0;
int ______________________________________________________________________________________________________________________________________________;
vector<int> t,sz, deg_max, nr_edge, times, low, good;
vector<int> tin, tout;
vector<array<int,3>> pl;
void init(int n, int m, vector<int> U, vector<int> V, vector<int> W){
pl = vector<array<int,3>>(m + 1);
t.assign(n + 1,0);
sz.assign(n + 1,0);
deg_max.assign(n + 1, 0);
times.assign(n + 1, 0);
nr_edge.assign(n + 1, 0);
low.assign(n + 1, 1e9);
good.assign(n + 1,0);
tin.assign(n + 1,0);
tout.assign(n + 1,0);
vector<int> deg(n + 1);
for(int i = 1; i <= n; i++){
t[i] = i;
sz[i] =1;
}
for(int i = 1; i <= m; i++){
pl[i] = {U[i-1],V[i-1], W[i-1]};
}
sort(pl.begin() + 1, pl.begin() + 1 + m, [&](array<int,3> a,array<int,3> b){
return a[2] < b[2];
});
function<int(int)> root = [&](int nod){
while(t[nod] != nod) return root(t[nod]);
return nod;
};
function<void(int,int, int)> join = [&](int a, int b, int i){
deg[a]++;
deg[b]++;
int ra = root(a);
int rb = root(b);
if(sz[ra] > sz[rb]){
swap(ra,rb);
swap(a,b);
}
if(ra != rb){
times[ra] =i;
deg_max[rb] = max({deg_max[rb], deg[a],deg[b], deg_max[ra]});
good[rb] |= good[ra];
if(deg_max[rb] > 2){
good[rb] = 1;
low[rb] = min(low[rb], i);
}
t[ra] = t[rb];
sz[rb] += sz[ra];
}else{
if(!good[ra]){
good[ra] = 1;
low[ra] = i;;
}
}
};
for(int i = 1; i <= m; i++){
join(pl[i][0],pl[i][1],i);
}
vector<vector<int>> liste(n + 1);
for(int i = 1; i <= n; i++){
liste[i].push_back(t[i]);
liste[t[i]].push_back(i);
}
int cnt = 0;
function<void(int,int)> dfs = [&](int nod, int p){
tin[nod] = ++cnt;
for(auto i : liste[nod]){
if(i == p) continue;
dfs(i,nod);
}
tout[nod] = ++cnt;
};
int r = root(1);
dfs(r,r);
}
int is_ancestor(int u, int v){
return tin[u] <= tin[v] && tout[u] >= tout[v];
}
int getMinimumFuelCapacity(int u, int v){
if(is_ancestor(u,v)){
int nod = v;
while(t[nod] != u){
nod = t[nod];
}
if(good[u]){
return pl[max(times[nod],low[u])][2];
}else{
nod = u;
while(good[t[nod]] == 0){
nod = t[nod];
}
return pl[max(times[nod],low[t[nod]])][2];
}
}else if(is_ancestor(v,u)){
swap(u,v);
int nod = v;
while(t[nod] != u){
nod = t[nod];
}
if(good[u]){
return pl[max(times[nod],low[u])][2];
}else{
nod = u;
while(good[t[nod]] == 0){
nod = t[nod];
}
return pl[max(times[nod],low[t[nod]])][2];
}
}else{
int nod1 = v;
while(!is_ancestor(t[nod1],u)){
nod1 = t[nod1];
}
int nod2 = u;
while(!is_ancestor(t[nod2],v)){
nod2 = t[nod2];
}
if(times[nod1] < times[nod2]) swap(nod1,nod2);
if(good[t[nod1]]){
return pl[max(times[nod1],low[t[nod1]])][2];
}else{
int nod = t[nod1];
while(!good[t[nod]]){
nod = t[nod];
}
return pl[max(times[nod],low[t[nod]])][2];
}
}
}
// int32_t main(){
// cin.tie(0)->sync_with_stdio(0);
// int t = 1;
// if(red) cin >> t;
// // while(t--){
// // solve();
// // }
// }
/*
2 2 2 2 4
1 3 5
1 30
1 40
120 2
2 430
100 3
3 30
100 4
4 490
100 5
5 440
40 6
6 290
50 7
7 190
290 8
8 430
50 9
9 60
190 10
10 490
*/
Compilation message
swap.cpp: In member function 'void AIB::update(int, int)':
swap.cpp:176:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
176 | for(; pos < aib.size(); pos += (pos & -pos)){
| ~~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2071 ms |
336 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2071 ms |
336 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2071 ms |
336 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2071 ms |
336 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2071 ms |
336 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2071 ms |
336 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
