型
- primitive
using ll=long long; using ld=long double; using bo=bool; using ch=char; using st=string; using bi=bitset<1>; using ull=unsigned long long;
- container
template<class T>using ve=vector<T>; template<class T>using de=deque<T>; template<class T>using se=set<T>;
using vl=ve<ll>; using vd=ve<ld>; using vc=ve<ch>; using vs=ve<st>; using vb=ve<bi>;
c++のbool型vectorはカスなことで有名なのでbitset型vectorで代用
- pair, triple, quadruple
template<class T1, class T2>struct tuple2{ T1 a; T2 b; tuple2():a(),b(){} tuple2(T1 c, T2 d) { a=c,b=d; } auto operator<=>(const tuple2&) const=default; }; template<class T1, class T2, class T3>struct tuple3{ T1 a; T2 b; T3 c; tuple3():a(),b(),c(){} tuple3(T1 d, T2 e, T3 f) { a=d,b=e,c=f; } auto operator<=>(const tuple3&) const=default; }; template<class T1, class T2, class T3, class T4>struct tuple4{ T1 a; T2 b; T3 c; T4 d; tuple4():a(),b(),c(),d(){} tuple4(T1 e, T2 f, T3 g, T4 h) { a=e,b=f,c=g,d=h; } auto operator<=>(const tuple4&) const=default; }; template<class T1, class T2>using pa=tuple2<T1,T2>; template<class T1, class T2, class T3>using tri=tuple3<T1,T2,T3>; template<class T1, class T2, class T3, class T4>using quad=tuple4<T1,T2,T3,T4>;
マクロ
#define all(c) (c).begin(),(c).end() // begin to end #define allr(c) (c).rbegin(),(c).rend() // begin to end reverse #define debug(...) { cerr<<#__VA_ARGS__<<" = ";DEBUG(__VA_ARGS__); } // debug #define debug1d(c) fori(x,0,lsz(c)) { cerr<<'['<<x<<']'<<c[x]; } DEBUG(); // debug1d #define debug2d(c) fori(y,0,lsz(c)) { cerr<<'['<<y<<']'<<sp; debug1d(c[y]); } // debug2d #define fori1(i,c) for(ll i=0;i<lsz(c);i++) // for index container #define fori2(i,f,l) for(ll i=f;i<l;i++) // for index f to l #define fori_overload(a,b,c,x,...) x // for index overload #define fori_args(a) fori_overload a // for index args #define fori(...) fori_args((__VA_ARGS__,fori2,fori1,~))(__VA_ARGS__) // for index #define forir1(i,c) for(ll i=lsz(c)-1;-1<i;i--) // for index container reverse #define forir2(i,f,l) for(ll i=f;l<i;i--) // for index f to l reverse #define forir_overload(a,b,c,x,...) x // for index overload reverse #define forir_args(a) forir_overload a // for index args reverse #define forir(...) fori_args((__VA_ARGS__,forir2,forir1,~))(__VA_ARGS__) // for index reverse #define forx_overload(a,b,c,d,x,...) x // for each overload #define forx_args(a) forx_overload a // for each args #define forx(...) forx_args((__VA_ARGS__,forx3,forx2,forx1,~))(__VA_ARGS__) // for each #define forx1(x,c) for(auto& x:c) // for each x #define forx2(x,y,c) for(auto& [x,y]:c) // for each xy #define forx3(x,y,z,c) for(auto& [x,y,z]:c) // for each xyz #define forx_overload(a,b,c,d,x,...) x // for each overload #define forx_args(a) forx_overload a // for each args #define forx(...) forx_args((__VA_ARGS__,forx3,forx2,forx1,~))(__VA_ARGS__) // for each #define forxr1(x,c) for(auto& x:adaptors::reverse(c)) // for each x reverse #define forxr2(x,y,c) for(auto& [x,y]:adaptors::reverse(c)) // for each xy reverse #define forxr3(x,y,z,c) for(auto& [x,y,z]:adaptors::reverse(c)) // for each xyz reverse #define forxr_overload(a,b,c,d,x,...) x // for each overload #define forxr_args(a) forx_overload a // for each args #define forxr(...) forxr_args((__VA_ARGS__,forxr3,forxr2,forxr1,~))(__VA_ARGS__) // for each #define lam(...) =[&](__VA_ARGS__)-> // lambda #define lamb [&] // lambda begin #define lame () // lambda end #define inll(...) ll __VA_ARGS__; IN(__VA_ARGS__); // input ll #define inld(...) ld __VA_ARGS__; IN(__VA_ARGS__); // input ld #define inch(...) ch __VA_ARGS__; IN(__VA_ARGS__); // input ch #define instr(...) str __VA_ARGS__; IN(__VA_ARGS__); // input str #define indl(name,sz) dl name(sz); IN(name); // input dl #define invl(name,sz) vl name(sz); IN(name); // input vl #define inves(name,sz) vs name(sz); IN(name); // input ves #define invvl(name,y,x) vvl name(y,vl(x)); IN(name); // input vevell #define invpll(name,sz,afix,bfix) vpll name(sz); INVP(name,afix,bfix); // input vepall #define in_graph(name,vsz,esz,vifix) graph name(vsz); ING(name,esz,vifix); // input graph #define in_directed_graph(name,vsz,esz,vifix) graph<ll> name(vsz); INDG(name,esz,vifix); // input directed graph #define in_weighted_graph(name,vsz,esz,vifix) graph<ll> name(ndsz); INWG(name,esz,vifix); // input weighted graph #define in_weighted_directed_graph(name,vsz,esz,vifix) graph<ll> name(vsz); INWDG(name,esz,vifix); // input weighted directed graph
for系は可変引数マクロのテクニックを利用
https://blog.miz-ar.info/2015/12/c-variadic-macro/
関数
- at
template<class T>auto at(T& c, ll i, ll r=0){ if(r==-1) return (i<0)?c[-i-1]:c[lsize(c)-1-i]; return (i<0)?c[lsize(c)+i]:c[i]; } template<class T>auto atr(T& c, ll i, ll r=0){ return (r==-1)?at(c,i):at(c,-i-1); }
pythonを参考にコンテナを負のインデックスで取得出来るようにした関数
auto at(T& c, ll i, ll r=0): r=0のとき先頭[0]末尾[-1]として取得しr=1のとき末尾[0]先頭[-1]として取得する
auto atr(T& c, ll i, ll r=0): r=0のとき先頭[-1]末尾[0]として取得しr=1のとき先頭[0]末尾[-1]として取得する
- bit
ll bpopcnt(ll x){ return popcount((unsigned long long)x); } bo btest(ll x, ll i){ return (62<i)?0:x&(1ll<<i); } void bset(ll& x, ll i, bo b){ (b)?x|=(1ll<<i):x&=~(1ll<<i); }
ll bpopcnt(ll x); C++20のpopcountと同じだが引数をll型で受け取ることが出来る
bo btest(ll x, ll i); 整数xのi番目ビットが0か1か返す
void bset(ll& x, ll i, bo b); 整数xのi番目ビットをb=0/1にセットする
- get
template<ll i, class T1, class T2>auto& get(const pa<T1,T2>& p) { return (i==0)?p.a:p.b; } template<ll i, class T1, class T2, class T3>auto& get(const tri<T1,T2,T3>& t) { return (i==0)?t.a:(i==1)?t.b:t.c; } template<ll i, class T1, class T2, class T3, class T4>auto& get(const quad<T1,T2,T3,T4>& q) { return (i==0)?q.a:(i==1)?q.b:(i==2)?q.c:q.d; }
pa, tri, quad型のi番目の要素を取得する（std::getのオーバーロード）
- in
void in(){} template<class H, class ... T>void in(H& head, T& ... tail){ cin >> head; in(tail...); } template<class T, class U>void in(pa<T,U>& t){ cin>>t.a>>t.b; } template<class T>void in(ve<T>& v){ for(auto& e:v) in(e); } template<class T, class U>void invp(ve<pa<T,U>>& v){ for(auto& e:v) in(e.a,e.b); } void ing(graph<ll>& g, ll ndsz, ll edsz, ll ndfix) { g.resize(ndsz); rep(e,0,edsz) { ll i,j; cin>>i>>j,i+=ndfix,j+=ndfix,g[i].push_back({j,1}),g[j].push_back({i,1}); } } void indg(graph<ll>& g, ll ndsz, ll edsz, ll ndfix) { g.resize(ndsz); rep(e,0,edsz) { ll i,j; cin>>i>>j,i+=ndfix,j+=ndfix,g[i].push_back({j,1});} } void inwg(graph<ll>& g, ll ndsz, ll edsz, ll ndfix) { g.resize(ndsz); rep(e,0,edsz) { ll i,j,c; cin>>i>>j>>c,i+=ndfix,j+=ndfix,g[i].push_back({j,c}),g[j].push_back({i,c}); } } void inwdg(graph<ll>& g, ll ndsz, ll edsz, ll ndfix) { g.resize(ndsz); rep(e,0,edsz) { ll i,j,c; cin>>i>>j>>c,i+=ndfix,j+=ndfix,g[i].push_back({j,c}); } }
某レッドコーダーのコードを写経した
pythonのように変数宣言と入力を同時に可能にした関数でマクロから呼び出す
- orange
template <class T> bool orange(ll x, ve<T>& v) { return (x<0||ll(v.size())<= x); } template <class T> bool orange(ll y, ll x, ve<ve<T>>& v) { return (y<0||ll(v.size())<=y||x<0||ll(v[y].size())<=x); }
一次元または二次元コンテナに対してインデックス[y][x]が範囲外かどうかチェックする
- out
void out(){ cout<<en; } template<class H, class ... T>void out(H head, T ... tail){ cout<<fixed<<setprecision(8)<<head; out(tail...); } template <class C> void outsp(C& c){ for(auto& e:c) cout<<e<<sp; cout<<en; } template <class C> void outel(C& c){ for(auto& e:c) cout<<e<<en; }
コンテナの内容を一括して出力する
- pop, push
auto pop(auto& c, ll i=inf){ auto r=c[(i==inf)?lsize(c)-1:i]; if(i!=inf)rep(j,i+1,lsize(c)) c[j-1]=c[j]; c.pop_back(); return r; } void push(auto& c, auto x, ll i=inf){ return (i!=inf)?(void)c.insert(c.begin()+i,x):c.push_back(x); }
C++のpopは不便なのでpopと同時に値も取得できるようにした
auto pop(auto& c, ll i=inf): cのi番目要素をpopする
（iをsize以上に指定したときはpopbackでO(1)、それ以外はデータ構造依存の計算量）
void push(auto& c, auto x, ll i=inf): cのi番目に値xをpushする
（iをsize以上に指定したときはpushbackでO(1)、それ以外はデータ構造依存の計算量）
- tsort
template<ll i, class T>void tsort(T b, T e) { sort(b,e,[&](const auto& l, const auto& r){return get<i>(l)<get<i>(r);}); }
tuple型コンテナに対してi番目の要素に着目してソートする
- trim
template <class T> T trim(T& c, ll l, ll r) { T t; umin(r,lsize(c)); rep(i,l,r) push(t,c[i]); return t; }
半開区間[l,r)でコンテナをトリミングして返す
ソースコード
#include <bits/stdc++.h> using namespace std; #include <atcoder/all> using namespace atcoder; #define BOOST #ifdef BOOST #include <boost/dynamic_bitset.hpp> #include <boost/multiprecision/cpp_int.hpp> #include <boost/multiprecision/cpp_dec_float.hpp> #include <boost/range/adaptors.hpp> using namespace boost; using mpi=multiprecision::cpp_int; using mpf=multiprecision::cpp_dec_float_100; #endif using ll=long long; using ld=long double; using ch=char; using bo=bool; using vo=void; using ull=unsigned long long; using str=string; template<class T> using vec=vector<T>; template<class T> using deq=deque<T>; using dbit=dynamic_bitset<>; template<class T>using uset=unordered_set<T>; template<class A, class B> using umap=unordered_map<A,B>; using cll=const ll; using cld=const ld; using cch=const ch; using cbo=const bo; using cull=const ull; using cstr=const str; template<class T, class U>struct tuple2 { T a; U b; tuple2():a(),b(){} tuple2(T c, U d) { a=c,b=d; } auto operator<=>(const tuple2&) const=default; tuple2& operator=(const pair<T,U>& r) { a=r.first,b=r.second; return *this; } tuple2(pair<T,U> p):a(p.first),b(p.second){} operator pair<T,U>() const { return pair<T,U>{a,b}; } }; template<class T, class U, class V>struct tuple3 { T a; U b; V c; tuple3():a(),b(),c(){} tuple3(T d, U e, V f) { a=d,b=e,c=f; } auto operator<=>(const tuple3&) const=default; }; template<class T1, class T2, class T3, class T4>struct tuple4 { T1 a; T2 b; T3 c; T4 d; tuple4():a(),b(),c(),d(){} tuple4(T1 e, T2 f, T3 g, T4 h) { a=e,b=f,c=g,d=h; } auto operator<=>(const tuple4&) const=default; }; template<class T1, class T2>using pai=tuple2<T1,T2>; template<class T1, class T2, class T3>using tri=tuple3<T1,T2,T3>; template<class T, class U, class V, class W>using qua=tuple4<T,U,V,W>; using pll=pai<ll,ll>; using psl=pai<str,ll>; using tlll=tri<ll,ll,ll>; using qllll=qua<ll,ll,ll,ll>; using vl=vec<ll>; using vc=vec<ch>; using vb=vec<bitset<1>>; using vs=vec<str>; using vpll=vec<pll>; using vtlll=vec<tlll>; using dl=deque<ll>; using dc=deque<ch>; using ds=deque<str>; using sl=set<ll>; using sc=set<ch>; using ss=set<str>; using mll=map<ll,ll>; using mlb=map<ll,bo>; using mcc=map<ch,ch>; using mcl=map<ch,ll>; using mss=map<str,str>; using vvl=vec<vl>; struct edge { ll vi=ll(); ll ex=ll(); }; using graph=vector<vector<edge>>; bo operator!(bitset<1> b) { return b==false; } #define all(c) (c).begin(),(c).end() // begin to end #define allr(c) (c).rbegin(),(c).rend() // begin to end reverse #define debug(...) { cerr<<#__VA_ARGS__<<" = ";DEBUG(__VA_ARGS__); } // debug #define debug1d(c) fori(x,0,lsz(c)) { cerr<<'['<<x<<']'<<c[x]; } DEBUG(); // debug1d #define debug2d(c) fori(y,0,lsz(c)) { cerr<<'['<<y<<']'<<sp; debug1d(c[y]); } // debug2d #define fori1(i,c) for(ll i=0;i<lsz(c);i++) // for index container #define fori2(i,f,l) for(ll i=f;i<l;i++) // for index f to l #define fori_overload(a,b,c,x,...) x // for index overload #define fori_args(a) fori_overload a // for index args #define fori(...) fori_args((__VA_ARGS__,fori2,fori1,~))(__VA_ARGS__) // for index #define forir1(i,c) for(ll i=lsz(c)-1;-1<i;i--) // for index container reverse #define forir2(i,f,l) for(ll i=f;l<i;i--) // for index f to l reverse #define forir_overload(a,b,c,x,...) x // for index overload reverse #define forir_args(a) forir_overload a // for index args reverse #define forir(...) fori_args((__VA_ARGS__,forir2,forir1,~))(__VA_ARGS__) // for index reverse #define forx_overload(a,b,c,d,x,...) x // for each overload #define forx_args(a) forx_overload a // for each args #define forx(...) forx_args((__VA_ARGS__,forx3,forx2,forx1,~))(__VA_ARGS__) // for each #define forx1(x,c) for(auto& x:c) // for each x #define forx2(x,y,c) for(auto& [x,y]:c) // for each xy #define forx3(x,y,z,c) for(auto& [x,y,z]:c) // for each xyz #define forx_overload(a,b,c,d,x,...) x // for each overload #define forx_args(a) forx_overload a // for each args #define forx(...) forx_args((__VA_ARGS__,forx3,forx2,forx1,~))(__VA_ARGS__) // for each #define forxr1(x,c) for(auto& x:adaptors::reverse(c)) // for each x reverse #define forxr2(x,y,c) for(auto& [x,y]:adaptors::reverse(c)) // for each xy reverse #define forxr3(x,y,z,c) for(auto& [x,y,z]:adaptors::reverse(c)) // for each xyz reverse #define forxr_overload(a,b,c,d,x,...) x // for each overload #define forxr_args(a) forx_overload a // for each args #define forxr(...) forxr_args((__VA_ARGS__,forxr3,forxr2,forxr1,~))(__VA_ARGS__) // for each #define lam(...) =[&](__VA_ARGS__)-> // lambda #define lamb [&] // lambda begin #define lame () // lambda end #define inll(...) ll __VA_ARGS__; IN(__VA_ARGS__); // input ll #define inld(...) ld __VA_ARGS__; IN(__VA_ARGS__); // input ld #define inch(...) ch __VA_ARGS__; IN(__VA_ARGS__); // input ch #define instr(...) str __VA_ARGS__; IN(__VA_ARGS__); // input str #define indl(name,sz) dl name(sz); IN(name); // input dl #define invl(name,sz) vl name(sz); IN(name); // input vl #define inves(name,sz) vs name(sz); IN(name); // input ves #define invvl(name,y,x) vvl name(y,vl(x)); IN(name); // input vevell #define invpll(name,sz,afix,bfix) vpll name(sz); INVP(name,afix,bfix); // input vepall #define in_graph(name,vsz,esz,vifix) graph name(vsz); ING(name,esz,vifix); // input graph #define in_directed_graph(name,vsz,esz,vifix) graph<ll> name(vsz); INDG(name,esz,vifix); // input directed graph #define in_weighted_graph(name,vsz,esz,vifix) graph<ll> name(ndsz); INWG(name,esz,vifix); // input weighted graph #define in_weighted_directed_graph(name,vsz,esz,vifix) graph<ll> name(vsz); INWDG(name,esz,vifix); // input weighted directed graph const ch en='\n'; // endl const ch sp=' '; // space const ll inf=2000000000000000000; // infinity 2e18 const ll abc_max=26; // alphabet max size const ll llong_max=9223372036854775807; // 9e18 const ld pi=numbers::pi; // 3.14 const ll mod1=1000000007; // mod 1e9+7 const ll mod9=998244353; // mod 998244353 ll bcnt(ll x,ll b); bo bget(ll x,ll i); ll blen(ll x); vo bset(ll &x,ll i,bo b); vo copy(const auto& f, auto& t); vl degin(graph& g); vl degout(graph& g); template<class C>ll lower_bound_index(C& c, auto x); template<class C>auto lower_bound_value(C& c, auto x); template<class C>ll upper_bound_index(C& c, auto x); template<class C>auto upper_bound_value(C& c, auto x); ll ldiv(ll a,ll b,bo ceil); ll llog(ll a, ll b, bo u); ll lpow(ll x, ll n); ll lsz(auto& c); str tostr(ll x); str tolower(cstr& s); str toupper(cstr& s); void DEBUG(void); void DEBUG(auto x); template<class H, class ... T>void DEBUG(H head, T ... tail); void IN(); template<class H, class...T>void IN(H& head, T&...tail); template<template<class...>class TE, class TY>struct IST; template<template<class...>class TE, class...A>struct IST<TE,TE<A...>>; ll at(auto& c,ll i) { return i<0?lsz(c)+i+abs(abs(i+1)/lsz(c))*lsz(c):i-(i/lsz(c))*lsz(c); } ll atr(auto& c,ll i) { return i<0?(abs(i)-1)-((abs(i)-1)/lsz(c))*lsz(c):lsz(c)-1-(i-(i/lsz(c))*lsz(c)); } ll bcnt(ll x,ll b) { return (b)?popcount(ull(x)):llog(2,x,true)-popcount(ull(x)); } bo bget(ll x,ll i) { return (62<i)?0:bo(x&(1ll<<i)); } ll blen(ll x) { return llog(2,x,true); } vo bset(ll& x,ll i,bo b) { (b)?(x|=(1ll<<i)):(x&=~(1ll<<i)); } vo copy(const auto& f,auto& t) { if(lsz(t)<lsz(f)) t.resize(lsz(f)); fori(i,0,lsz(f)) t[i]=f[i]; } vl degin(graph& g) { vl deg(lsz(g)); fori(i,0,lsz(g)) for(auto& [vj,ey]:g[i]) deg[vj]++; return deg; } vl degout(graph& g) { vl deg(lsz(g)); fori(i,0,lsz(g)) deg[i]+=lsz(g[i]); return deg; } template<class C>ll lower_bound_index(C& c,auto x) { return lower_bound(all(c),x)-c.begin(); } template<class C>auto lower_bound_value(C& c,auto x) { if constexpr(IST<set,C>::value) return *c.lower_bound(x); else return *lower_bound(all(c),x); } template<class C>ll upper_bound_index(C& c,auto x) { return upper_bound(all(c),x)-c.begin(); } template<class C>auto upper_bound_value(C& c,auto x) { if constexpr(IST<set,C>::value) return *c.upper_bound(); else return *upper_bound(all(c),x); } template<class C>bo findb(C& c, auto x) { if constexpr(is_same_v<str,C>) { str p=x; return search(all(c),boyer_moore_searcher(all(p)))!=c.end(); } else if constexpr(IST<set,C>::value) return c.find()!=c.end(); else return find(all(c),x)!=c.end(); } template<class C>ll findi(C& c, auto x) { if constexpr(is_same_v<str,C>) { str p=x; auto i=search(all(c),boyer_moore_searcher(all(p))); return (i==c.end())?inf:i-c.begin(); } else { auto i=find(all(c),x); return (i==c.end())?inf:i-c.begin(); } } template<ll i,class T1,class T2>auto& get(const pai<T1,T2>& p) { return (i==0)?p.a:p.b; } template<ll i,class T1,class T2,class T3>auto& get(const tri<T1,T2,T3>& t) { return (i==0)?t.a:(i==1)?t.b:t.c; } template<ll i,class T1,class T2,class T3,class T4>auto& get(const qua<T1,T2,T3,T4>& q) { return (i==0)?q.a:(i==1)?q.b:(i==2)?q.c:q.d; } template <class C> ll lcnt(C& c) { return ll(c.count()); } template <class C, class X> ll lcnt(C& c, X x) { return ll(count(all(c),x)); } ll ldiv(ll a, ll b, bo ceil){ return (!!ceil)?(a+b-1)/b:a/b; } template<class C>ll lfind(C& c, auto x) { if constexpr(is_same_v<str,C>) return (c.find(x)==str::npos)?0:1; else return (c.find(x)==c.end())?0:1; } ll llog(ll a, ll b, bo ceil) { ll now = 1, res = (!!ceil) ? 1 : 0; while (now < b) res++, now *= a; return (now != b) ? res - 1 : res; } ll lpow(ll x, ll n) { if(n<0) return 0; if(x==2) return (1ll<<n); ll z=1; fori(i,0,n) z*=x; return z; } ll lsz(auto& t){ return (ll)t.size(); } ll llen(ll x){ return (ll)tostr(x).size(); } void out(){ cout<<en; exit(0); } template<class H, class...T>void out(H head, T ... tail){ cout<<fixed<<setprecision(8)<<head; out(tail...); } template <class C> void outsp(C& c){ for(auto& e:c) cout<<fixed<<setprecision(8)<<e<<sp; out(); } template <class C> void outen(C& c){ for(auto& e:c) cout<<fixed<<setprecision(8)<<e<<en; out(); } template<class T>auto pop(T& c, ll i=inf){ if(i==inf) { auto r=c.back(); c.pop_back(); return r; } auto r=c[min(lsz(c)-1,i)]; fori(j,i+1,lsz(c)) c[j-1]=c[j]; c.pop_back(); return r; } template<class T>auto popb(T& c) { auto r=c.back(); c.pop_back(); return r; } template<class T>auto popf(T& c) { auto r=c.front(); c.pop_front(); return r; } template<class T>void push(T& c, auto x, ll i=inf){ if constexpr(IST<set,T>::value) c.insert(x); else c.insert(c.begin()+min(lsz(c),i),x); } template<class T>vo pushb(T& c, auto x) { if constexpr(IST<set,T>::value) c.insert(x); else c.push_back(x); } template<class T>vo pushf(T& c, auto x) { if constexpr(IST<set,T>::value) c.insert(x); else c.push_front(x); } ch toch(ll x) { return ch(x+48); } str tostr(ll x) { return to_string(x); } ll toll(ch c) { return ll(c)-48; } ll toll(str& s) { return stoll(s); } str tolower (cstr& s){ str res; forx(x,s) push(res,tolower(x)); return res; } str toupper(cstr& s){ str res; forx(x,s) push(res,toupper(x)); return res; } template <class T> void itr_next(T& itr, ll INF) { if (*itr != INF) ++itr; } template <class T> void itr_prev(T& itr, ll INF) { if (*itr != INF) --itr; } template<class T>void make2d(T& cc, ll ys, ll xs) { cc.resize(ys); fori(y,0,ys) cc[y].resize(xs); } template<class T, class X>void make2d(T& cc, ll ys, ll xs, X x) { cc.resize(ys); fori(y,0,ys) cc[y].resize(xs,x); } bo range(ll x, auto& c) { return 0<=x&&x<lsz(c); } bo range(ll y, ll x, auto& c) { return 0<=y&&y<lsz(c)&&0<=x&&x<lsz(c[y]); } auto reverse_graph(graph& g) { graph res(lsz(g)); fori(i,0,lsz(g)) for(auto& [j,c]:g[i]) res[j].push_back({i,c}); return res; } template <class T1, class ... T2> bool umax(T1& x, T2 ... args) { x=max({x,args...}); return !(max({args...})<x); } template <class T1, class ... T2> bool umin(T1& x, T2 ... args) { x=min({x,args...}); return !(x<min({args...}));} template <class T> T trim(T& c, ll l, ll r) { T t=T(); umin(r,lsz(c)); fori(i,l,r) push(t,c[i]); return t; } template<ll i>void tsort(auto b, auto e) { sort(b,e,[&](const auto& l, const auto& r){return get<i>(l)<get<i>(r);}); } void DEBUG(void) { cerr<<en; } void DEBUG(auto x) { cerr<<x<<en; } template<class H, class ... T>void DEBUG(H head, T ... tail){ cerr<<fixed<<setprecision(8)<<head<<','; DEBUG(tail...); } void IN(){} template<class H, class ... T>void IN(H& head, T& ... tail){ cin>>head; IN(tail...); } template<class T, class U>void IN(pai<T,U>& p){ cin>>p.a>>p.b; } template<class T>void IN(deq<T>& v) { forx(e,v) IN(e); } template<class T>void IN(vec<T>& v) { forx(e,v) IN(e); } void INVP(auto& v, auto afix, auto bfix){ forx(e,v) IN(e.a,e.b),e.a+=afix,e.b+=bfix; } void ING(graph& g, ll esz, ll vifix) { ll vi,nvi; fori(e,0,esz) cin>>vi>>nvi,push(g[vi+vifix],edge{nvi+vifix,1}),push(g[nvi+vifix],edge{vi+vifix,1}); } void INDG(graph& g, ll edsz, ll ndfix) { fori(e,0,edsz) { ll i,j; cin>>i>>j,i+=ndfix,j+=ndfix,g[i].push_back({j,1});} } void INWG(graph& g, ll edsz, ll ndfix) { fori(e,0,edsz) { ll i,j,c; cin>>i>>j>>c,i+=ndfix,j+=ndfix,g[i].push_back({j,c}),g[j].push_back({i,c}); } } void INWDG(graph& g,ll edsz,ll ndfix) { fori(e,0,edsz) { ll i,j,c; cin>>i>>j>>c,i+=ndfix,j+=ndfix,g[i].push_back({j,c}); } } template<template<class...>class TE, class TY>struct IST:std::false_type {}; template<template<class...>class TE, class...A>struct IST<TE,TE<A...>>:std::true_type {};
