#include #include using namespace std; using namespace atcoder; #define INF 1LL<<60 #define MOD 998244353 #define MMOD 1000000007 using mint=modint998244353; using ll=long long; using ull=unsigned long long; using ld=long double; template using vc=vector; template using vv=vc>; using vl=vector; using vvl=vv; using vs=vc; using vvs=vv; using vb=vc; using vvb=vv; using lP=pair; using vlp=vc; template bool chmin(T& a, T b){if(a > b){a = b; return true;} return false;} template bool chmax(T& a, T b){if(a < b){a = b; return true;} return false;} #define YES cout<<"Yes"<>; vl dx={0,0,1,-1}; vl dy={1,-1,0,0}; vector dijkstra(Graph &G,ll s){ vl dist(ll(G.size()),INF); priority_queue,vector,greater> pq; dist[s]=0; pq.push({0,s}); while(!pq.empty()){ lP p=pq.top(); ll d=p.first; ll v=p.second; pq.pop(); if(d>dist[v]) continue; for(auto &e:G[v]){ if(d+e.weight=h||x>=w||y<0||x<0); }; //Gにグラフ、sがスタート地点。sからの距離が返り値の配列に入る。 vl bfs(vvl &G,ll s){ vl dist(G.size(),INF); queue q; dist[s]=0; q.push(s); while(!q.empty()){ ll v=q.front(); q.pop(); for(auto &e:G[v]){ if(dist[e] != INF) continue; dist[e]=dist[v]+1; q.push(e); } } return dist; }; //壁がある時にcontinueするならコメントアウト外して! vvl gridbfs(vs &G,ll sy,ll sx){ vvl dist(G.size(),vl(G[0].size(),INF)); queue q; dist[sy][sx]=0; q.push(make_pair(sy,sx)); while(!q.empty()){ lP p=q.front(); ll y=p.first; ll x=p.second; q.pop(); for(int i=0;i<4;i++){ ll ny=y+dy[i]; ll nx=x+dx[i]; if(outgrid(ny,nx,G.size(),G[0].size())) continue; if(dist[ny][nx]!=INF) continue; // if(g[ny][nx]=='#') continue; dist[ny][nx]=dist[y][x]+1; q.push(make_pair(ny,nx)); } } return dist; } vb vi; //Gにグラフ、nowが今の場所。この分の上にvisited書いてね。main内でviをresizeもしてね。 void dfs(vvl &G,ll now){ vi[now]=true; for(auto &e:G[now]){ if(vi[e]) continue; dfs(G,e); } }; ll pathcnt=0; //n頂点全てを通るパスが何通りあるかをpathcntに記憶する。上にn宣言、main内でviをresizeしてね。cntは最初は1。コメントアウト外してね。 void pathdfs(vvl &G,ll now,ll cnt){ vi[now]=true; //if(cnt==n) pathcnt++; for(auto &e:G[now]){ if(vi[e]) continue; pathdfs(G,e,cnt+1); } vi[now]=false; } vv visi; ll h,w; //グリッド上DFS。探索して行けるとこはvisiがtrue,行けないとこはfalse。visiとh,wを上に!main内でresizeも! void on_the_grid_dfs(vs &G,ll y,ll x){ visi[y][x]=true; for(int i=0;i<4;i++){ ll nx=x+dx[i]; ll ny=y+dy[i]; if(outgrid(ny,nx,h,w)) continue; if(visi[ny][nx]) continue; on_the_grid_dfs(G,ny,nx); } }; struct unionfind{ vl par,rank,siz; //par(x)=要素xの親頂点の番号(自身が根の場合は-1 //rank(x)=要素xの属する根付き木の高さ //siz(x)=要素xの属する根付き木に含まれる超点数 unionfind(int n) :par(n,-1),rank(n,0),siz(n,1) { } ll root(ll x){ if(par[x]==-1) return x; else return par[x]=root(par[x]); } bool issame(ll x,ll y){ return root(x)==root(y); } void unite(ll x,ll y){ x=root(x); y=root(y); if(x==y) return ; if(rank[x]> RLE(string s){ vector> rle; for(char c:s){ if(rle.empty() || rle.back().first != c) rle.emplace_back(c,1); else rle.back().second++; } return rle; }; //2進数から10進数へ ll base2to10(string s){ ll n=s.size(); ll ans=0; ll a=1; reverse(s.begin(),s.end()); for(int i=0;i digits={'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'}; do{ ans+=digits[n%x]; n/=x; }while(n); reverse(ans.begin(),ans.end()); return ans; }; ld manhattan(ld x,ld y,ld x2,ld y2){ return (abs(x-x2)+abs(y-y2)); }; ll gcd(ll a,ll b){ while(a>=1&&b>=1){ if(a=1) return a; return b; } //nを素因数分解して、pairで(素数,指数)が返される。 vlp pfact(ll n){ vlp a; for(ll i=2;i*i<=n;i++){ if(n%i!=0) continue; ll ex=0; while(n%i==0){ ex++; n/=i; } a.emplace_back(i,ex); } if(n!=1) a.emplace_back(n,1); return a; } //nを素因数分解して、配列で素数が返される。(総積がnになる) vl pfact2(ll n){ vl a; for(ll i=2;i*i<=n;i++){ while(n%i==0){ n/=i; a.push_back(i); } } if(n!=1) a.push_back(n); return a; } //n以下の整数について素数判定をしてnまでの素数が昇順に入ってる配列を返す。 vl eratosthenes(ll n){ vb isprime(n,false); vl p; for(int i=2;i>n; set se; vs s(n),t(n); for(int i=0;i>s[i]>>t[i]; } for(int i=0;i