I got bored with solving and wanted to do something which is related to cp and also very fun so i decided to write this tutorial.bare me for my bad English .
how to solve grid problems
here is my template to solve grid problems
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
string ds="RLDU";
int n,m;
bool possible(int x,int y){
//cout<<n<<" "<<m<<" "<<x<<" "<<y<<" possible"<<endl;
return (x<n&&x>=0&&y<m&&y>=0);
}
here we cand do just x+dx[i],y+dx[i] to move the four
directions and ds helps if we want to record path.
we can easily extend it to include four diagonals
1) counting rooms
For each unvisited '.' cell we have to make dfs(or bfs)
and keep on coloring the visited nodes.We keep track number
of dfs by count variable .our answer would be count.
void dfs(int x,int y){
if(!possible(x,y)||vis[x][y]!=-1||grid[x][y]==0)return ;
vis[x][y]=1;
int i;
fo(i,0,4){
int nx=x+dx[i],ny=y+dy[i];
dfs(nx,ny);
}
}
fo(i,0,n){
string s;
cin>>s;
fo(j,0,m){
if(s[j]=='.')grid[i][j]=1;
else grid[i][j]=0;
}
}
int ans=0;
fo(i,0,n){
fo(j,0,m){
if(grid[i][j]==1&&vis[i][j]==-1){
dfs(i,j);
ans++;
}
}
}
cout<<ans<<endl;
2) Labyrinth
We will store the coordinates of a and b ,now we start bfs
from a and try to reach b. We will keep a vector FRM and
DIR which will keep track of the cell from which we came here
and what is the direction of that move .At last if b is visited
we will go in reverse order by using FRM and try to recreate the path.
here a,b is coordinate of 'A' and c,d is coordinate of 'B'
queue<pii> q;
q.push({a,b});
vii from[n+1][m+1];
from[a][b].pb({0,0});
char ch[n+1][m+1];
while(!q.empty()){
pii p=q.front();
x=p.x;
y=p.y;
// cout<<from[x][y][0].x<<" "<<from[x][y][0].y<<" "<<x<<" "<<y<<" : ";
q.pop();
vis[x][y]=1;
if(grid[x][y]==3)break;
fo(i,0,4){
int nx=x+dx[i],ny=y+dy[i];
//cout<<x<<" "<<dx[i]<<","<<y<<" "<<dy[i]<<endl;
if(!possible(nx,ny))continue;
if(grid[nx][ny]==0||vis[nx][ny]!=-1)continue;
//cout<<"("<<nx<<","<<ny<<") ";
vis[nx][ny]=1;
q.push({nx,ny});
from[nx][ny].pb(p);
ch[nx][ny]=ds[i];
}
//cout<<endl;
}
if(vis[c][d]==-1){
cout<<"NO"<<endl;
return 0;
}
else{
cout<<"YES"<<endl;
pii p={c,d};
while(p.x!=a||p.y!=b){
s+=ch[p.x][p.y];
p=from[p.x][p.y][0];
}
reverse(all(s));
cout<<s.size()<<endl;
cout<<s<<endl;
}
3) Building Roads
The problem is basically connecting the disconnected components.
do dfs on all unvisited nodes and save one node from each
connected component as a head node.Then if there are k connected
components connect their head node via k-1 edges between heads.
vi v;
fo(i,1,n+1){
if(vis[i]==-1){
v.pb(i);
dfs(i);
}
}
cout<<v.size()-1<<endl;
fo(i,1,v.size()){
cout<<v[i]<<" "<<v[i]-1<<endl;
}
4) Message Route
This question is similar to Labyrinth ,start a bfs from 1 and
also keep vector FRM to know from where the current node is reached
and at last if n is visited go in reverse order using FRM to recreate path.
queue<int> q;
q.push(1);
while(!q.empty()){
int p=q.front();
q.pop();
vis[p]=1;
if(p==n)break;
for(int aa:graph[p]){
if(vis[aa]==-1){
from[aa]=p;
vis[aa]=1;
q.push(aa);
}
}
}
vi v;
if(vis[n]==-1){
cout<<"IMPOSSIBLE"<<endl;
}
else{
v.pb(n);
a=n;
while(a!=1){
a=from[a];
v.pb(a);
}
cout<<v.size()<<endl;
rfo(i,v.size()-1,0){
cout<<v[i]<<" ";
}
}
5) Building teams
The question is about coloring the bipartite graphs more about it.
we try to color all vertex greedily if vertex is not visited color
it white and run dfs . now color all its uncolored neighbors of white vertex
black and vice versa and run dfs on them.
at last check that each edge has ends with different colors.
void dfs(int p,int c){
if(vis[p]!=-1){
return ;
}
vis[p]=1;
color[p]=c;
for(int aa:graph[p]){
if(vis[aa]==-1)dfs(aa,1-c);
}
}
bool ok=true;
_init(vis);
fo(i,1,n){
if(vis[i]==-1){
dfs(i,0);
}
}
fo(i,0,m){
if(color[edges[i].x]==color[edges[i].y]){
ok=false;
break;
}
}
if(!ok){
cout<<"IMPOSSIBLE"<<endl;
return 0;
}
fo(i,1,n+1){
cout<<color[i]+1<<" ";
}
6) Round Trip
Question is about finding cycle.We will run a dfs an keep vector VIS
to keep track of the nodes in the recusion stack.If we are at node p
we will run dfs no all of its childs if any of the child is in recursion
stack we will add this vertex to an array CYCLE . Now we will also keep
track of where to end cycle by TILL . If current is equal to TILL return from all dfs's else return TILL
int vis[N],from[N],color[N],till;
vi v;
int dfs(int p,int c){
//cout<<p<<" <<<"<<endl;
if(vis[p]!=-1){
till=p;
v.pb(p);
return 1;
}
vis[p]=1;
for(int aa:graph[p]){
if(aa==c)continue;
int x=dfs(aa,p);
//cout<<p<<" "<<aa<<" "<<x<<endl;
if(x==1){
v.pb(p);
if(till==p){
return 2;
}
else{
return 1;
}
}
else if(x==2)return 2;
}
vis[p]=2;
return 0;
}
7) Monsters
You have to do a multi source bfs from all the monsters . You keep track
of minimum step a monster can reach a cell in the GRID matrix
. Then you apply bfs from source and keep track of steps (initially 0)
and go to only those nodes where steps are less than grid[x][y] means
you only go to those cells where you can reach before any monster
has reached there. You can recreate path using FRM and DIR matrix as I have done in Labyrinth .
const int N=1001;
int grid[N][N];
string maze[N];
int vis[N][N];
signed main()
{
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int i,j,x;
cin>>n>>m;
string s;
vii mon;
int ax,ay;
fo(i,0,n){
cin>>s;
fo(j,0,m){
maze[i]=s;
if(s[j]=='A'){
ax=i;
ay=j;
}
if(s[j]=='M'){
mon.pb({i,j});
}
}
}
queue<pair<int,pii>> q;
_init(vis);
fo(i,0,mon.size()){
q.push({0,{mon[i].x,mon[i].y}});
vis[mon[i].x][mon[i].y]=1;
}
_init(grid);
while(q.size()>0){
pii p=q.front().y;
int lvl=q.front().x;
q.pop();
grid[p.x][p.y]=lvl;
fo(i,0,4){
int nx=p.x+dx[i],ny=p.y+dy[i];
if(!possible(nx,ny))continue;
if(maze[nx][ny]=='#')continue;
if(vis[nx][ny]!=-1)continue;
q.push({lvl+1,{nx,ny}});
vis[nx][ny]=1;
}
}
/*
fo(i,0,n){
fo(j,0,m){
cout<<grid[i][j]<<" ";
}
cout<<endl;
}
cout.flush();
*/
_init(vis);
pair<int,int> from[n+1][m+1];
char dir[n+1][m+1];
s="RLDU";
q.push({0,{ax,ay}});
pii to={-1,-1};
bool mm=mon.size()>0;
while(q.size()>0){
pii p=q.front().y;
int lvl=q.front().x;
q.pop();
if(grid[p.x][p.y]!=-1&&lvl>=grid[p.x][p.y]){
//cout<<p.x<<" "<<p.y<<" "<<lvl<<" "<<grid[p.x][p.y]<<endl;
continue;
}
//cout<<p.x<<" "<<p.y<<":";
if(p.x==0||p.x==n-1||p.y==0||p.y==m-1){
to={p.x,p.y};
break;
}
fo(i,0,4){
int nx=p.x+dx[i],ny=p.y+dy[i];
if(!possible(nx,ny))continue;
if(maze[nx][ny]=='#')continue;
if(vis[nx][ny]!=-1)continue;
if(grid[nx][ny]!=-1&&grid[nx][ny]<=lvl)continue;
from[nx][ny]=p;
q.push({lvl+1,{nx,ny}});
vis[nx][ny]=1;
dir[nx][ny]=s[i];
//cout<<"("<<nx<<","<<ny<<") ";
if(nx==0||nx==n-1||ny==0||ny==m-1){
//cout<<lvl<<" "<<
to={nx,ny};
break;
}
}
if(to.x!=-1)break;
//cout<<endl;
}
// cout<<to.x<<" "<<to.y<<" "<<ax<<" "<<ay<<endl;
if(to.x==-1){
cout<<"NO"<<endl;
return 0;
}
cout<<"YES"<<endl;
s="";
while(to.x!=ax||to.y!=ay){
s+=dir[to.x][to.y];
//cout<<to.x<<" "<<to.y
to=from[to.x][to.y];
}
reverse(all(s));
cout<<s.size()<<endl;
cout<<s<<endl;
return 0;
}
8) Shortest Routes I
The question ask you to implement simple dijsktra more about it
priority_queue<pii,vii,greater<pii>> q;
q.push({0,1});
_init(dis);
_init(vis);
dis[1]=0;
while(!q.empty()){
pii p=q.top();
q.pop();
int node=p.y,d=p.x;
if(vis[node]!=-1)continue;
vis[node]=1;
for(pii aa:graph[node]){
if(vis[aa.y]!=-1)continue;
if(dis[aa.y]==-1||dis[aa.y]>d+aa.x){
dis[aa.y]=d+aa.x;
q.push({d+aa.x,aa.y});
}
}
}
fo(i,1,n+1){
cout<<dis[i]<<" ";
}
9) Shortest Routes II
The question is about simple Floyd Warshall Algorithmmore about it
cin>>n>>m>>q;
fo(i,1,n+1){
fo(j,1,n+1){
mat[i][j]=inf;
}
mat[i][i]=0;
}
fo(i,0,m){
cin>>a>>b>>c;
mat[a][b]=min(mat[a][b],c);
mat[b][a]=min(mat[b][a],c);
}
int k;
fo(k,1,n+1){
fo(i,1,n+1){
fo(j,1,n+1){
mat[i][j]=min(mat[i][j],mat[i][k]+mat[k][j]);
}
}
}
fo(i,0,q){
cin>>a>>b;
cout<<((mat[a][b]>=inf)?-1:mat[a][b])<<"\n";
}
10) High scores
Let say we are at node k we have to find weather there is a positive cycle ending
at k and if there if a cycle whether there is a path like 1->k->n then ans is zero.
You can do this by runnig dfs for each node and see if there is cycle ending at
that node with positive sum.if there is no such cycle you have to find biggest
route from 1 to n. You can do this by using bellman ford complexity o(n*m)
const int N=2501;
vii graph[N];
int vis[N],dis[N],from1[N],to1[N],fromn[N],ton[N],cycle[N];
int n,m,r,has1,hasn;
int findc(int p){
vis[p]=1;
if(p==1){
has1=1;
}
if(p==n){
hasn=1;
}
for(pii aa:graph[p]){
if(aa.x==r){
dis[p]=max(dis[p],aa.y);
continue;
}
if(vis[aa.x]==1)continue;
if(vis[aa.x]==2){
dis[p]=max(dis[p],dis[aa.x]+aa.y);
}
else{
int x=findc(aa.x);
if(x!=-inf){
dis[p]=max(dis[p],x+aa.y);
}
}
}
vis[p]=2;
return dis[p];
}
signed main()
{
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int i,j,x;
cin>>n>>m;
int a,b,c;
fo(i,0,m){
cin>>a>>b>>c;
graph[a].pb({b,c});
}
fo(i,1,n+1){
_init(vis);
_init(dis);
has1=0;
hasn=0;
r=i;
fo(j,0,n)dis[j+1]=-inf;
x=findc(i);
//cout<<x<<" "<<has1<<" "<<hasn<<endl;;
to1[i]=has1;
ton[i]=hasn;
cycle[i]=x>0;
if(i==1){
fo(j,0,n)from1[j+1]=vis[j+1];
}
if(i==n){
fo(j,0,n)fromn[j+1]=vis[j+1];
}
}
fo(i,1,n+1){
if(cycle[i]){
if(from1[i]>0&&ton[i]>0){
cout<<-1;
return 0;
}
else if(fromn[i]>0&&to1[i]>0){
cout<<-1;
return 0;
}
}
}
//cout<<endl;
fo(i,0,n)dis[i+1]=-inf;
dis[1]=0;
fo(i,1,n+1){
fo(j,1,n+1){
if(dis[j]==-inf)continue;
for(pii aa:graph[j]){
dis[aa.x]=max(dis[aa.x],dis[j]+aa.y);
}
}
}
cout<<dis[n]<<endl;
return 0;
}
11) Flight Discounts
Find minimum distance from 1 till starting of edge and minimum distance
from end of node till n and add weight/2. may be the concept involved here
is called meet in the middle not sure though.create two graphs original and reverse.
from original graph start dijkstra from 1 and store result in FRM1 and from
reverse graph start dijkstra from n and store result in TON .then iterate
through all edges and ans is minimum of (FRM1[edge[i].start + edge.weight/2 + TON[edge.end])
_init(vis);
_init(dis);
dis[0]=0;
priority_queue<pii,vii,greater<pii>> q;
q.push({0,0});
while(!q.empty()){
pii p=q.top();
q.pop();
if(vis[p.y]!=-1)continue;
vis[p.y]=1;
for(pii aa:graph[p.y]){
if(vis[aa.x]!=-1)continue;
if(dis[aa.x]==-1||dis[aa.x]>p.x+aa.y){
q.push({p.x+aa.y,aa.x});
dis[aa.x]=p.x+aa.y;
}
}
}
vi f1;
fo(i,0,n){
f1.pb(dis[i]);
}
_init(vis);
_init(dis);
dis[n-1]=0;
//pl();
q.push({0,n-1});
while(!q.empty()){
pii p=q.top();
q.pop();
if(vis[p.y]!=-1)continue;
vis[p.y]=1;
//cout<<p.x<<" "<<p.y<<endl;
for(pii aa:rev[p.y]){
if(vis[aa.x]!=-1)continue;
if(dis[aa.x]==-1||dis[aa.x]>p.x+aa.y){
q.push({p.x+aa.y,aa.x});
dis[aa.x]=p.x+aa.y;
}
}
}
// pl();
vi fn;
fo(i,0,n){
fn.pb(dis[i]);
}
//cout<<f1<<endl;
//cout<<fn<<endl;
int ans=f1[n-1];
for(piii bb:edges){
pii aa=bb.y;
if(f1[aa.x]!=-1&&fn[aa.y]!=-1){
ans=min(ans,f1[aa.x]+fn[aa.y]+bb.x/2);
}
}
cout<<ans<<endl;
12)Finding Cycles
This problem can be solved using bellman ford algorithm .
the key idea is relax each edge n(number of node) times if there is no negative cycle
then because you should have got the final answer in n-1 iterations itself
which means if there is a negative cycle only then there will be some changes in nth iteration
so this way you can detect the cycle and you can regenerate if using FRM array
in depht explanation
cin>>n>>m;
int a,b,c;
fo(i,0,m){
cin>>a>>b>>c;
graph[a].pb({b,c});
}
fo(i,1,n+1)dis[i]=inf;
dis[1]=0;
vi baap(n+1,-1);
fo(i,0,n+1){
till=-1;
fo(j,1,n+1){
for(pii p:graph[j]){
if(dis[p.x]>dis[j]+p.y){
dis[p.x]=dis[j]+p.y;
baap[p.x]=j;
till=p.x;
}
}
}
}
if(till==-1){
cout<<"NO"<<endl;
return 0;
}
cout<<"YES"<<endl;
fo(i,0,n){
till=baap[till];
}
vi cyc;
for(int aa=till;;aa=baap[aa]){
cyc.pb(aa);
if(cyc.size()>1&&aa==till){
break;
}
}
reverse(all(cyc));
cout<<cyc<<endl;
13) Flight Routes
Important observaion here is k is very small (k<10) and
if you want to find k routes each vertex is visited atmax k times in k routes.
so it is someting like dijkstra you keep CNT array were you keep count of each node
and take a min heap(set or priority queue in cpp) and insert 1st node with cost 0
in it. Now let say p is smallest node in heap. increase count of p in CNT array
if it is more than k then continue to next iteration.if p is last node add cost
to ANS array.now iterate through all edges of p and add child with cost p.cost + edge weight
in the heap.
now just print ans array complexity o(mk).more about it
const int N=1e5+5;
vii graph[N];
int dis[N],vis[N];
signed main()
{
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int i,j,x,n,m,k;
cin>>n>>m>>k;
int a,b,c;
fo(i,0,m){
cin>>a>>b>>c;a--;b--;
graph[a].pb({b,c});
}
priority_queue<pii,vii,greater<pii>> q;
_init(dis);
_init(vis);
dis[0]=0;
q.push({0,0});
while(!q.empty()){
pii p=q.top();
q.pop();
if(vis[p.y]==1)continue;
vis[p.y]=1;
for(auto aa:graph[p.y]){
if(vis[aa.x]==-1){
if(dis[aa.x]==-1||dis[aa.x]>aa.y+p.x){
dis[aa.x]=aa.y+p.x;
q.push({dis[aa.x],aa.x});
}
}
}
}
/* fo(i,0,n){
cout<<dis[i]<<" ";
}*/
int count[n+1];
_init0(count);
vi v;
q.push({0,0});
int cnt=k;
while(!q.empty()&&count[n-1]<k){
pii p=q.top();
q.pop();
count[p.y]++;
if(p.y==n-1){
v.pb(p.x);
}
if(count[p.y]<=k){
for(auto aa:graph[p.y]){
q.push({p.x+aa.y,aa.x});
}
}
}
sort(all(v));
cout<<v<<endl;
return 0;
}
14) round trip 2
The quesiton is about finding cycle in a directed graph. there are 3 types of vertex in dfs
color 1: white = the vertex is completely unvisited.
color 2: grey = the vertex whose some but not all child are visited.
color 3: black = the vertex whose all the child are visited .
Now there will be a cycle only when the vertex you are currently on has a grey child.
So how will trace the cycle .we can do it by storing the end grey vertex in a variable.
and add all the vertex when going back in the recursion until that grey vertex is again visited.
more about it
detecting cycle in directed graph(video)
detecting cycle in directed graph gfg
int dfs(int p){
if(vis[p]!=-1)return 0;
vis[p]=1;
int x;
for(int aa:graph[p]){
if(vis[aa]==-1){
x=dfs(aa);
if(x!=0){
if(x==2)return x;
cycle.pb(p);
if(p==till)return 2;
else return 1;
}
}
else if(vis[aa]==1){
cycle.pb(aa);
cycle.pb(p);
till=aa;
return 1;
}
}
vis[p]=2;
return 0;
}
signed main()
{
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int i,j,x,n,m;
cin>>n>>m;
int a,b;
fo(i,0,m){
cin>>a>>b;
graph[a].pb(b);
}
_init(vis);
fo(i,1,n+1){
if(vis[i]==-1){
dfs(i);
}
if(cycle.size()>0)break;
}
if(cycle.size()==0){
cout<<"IMPOSSIBLE"<<endl;
}
else{
cout<<cycle.size()<<endl;
reverse(all(cycle));
cout<<cycle<<endl;
}
return 0;
}
15) Course Schedule
the problem is about simple topological sort.
more about it
topsort video
topsort tutorial cp algo
const int N=1e5+5;
vi graph[N],top;
int vis[N],till;
bool cycle;
void dfs(int p){
if(vis[p]!=-1)return ;
vis[p]=1;
int x;
for(int aa:graph[p]){
if(vis[aa]==1){
cycle=true;
}
else if(vis[aa]==-1){
dfs(aa);
}
if(cycle)return;
}
vis[p]=2;
top.pb(p);
return ;
}
signed main()
{
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int i,j,x,n,m;
cin>>n>>m;
int a,b;
fo(i,0,m){
cin>>a>>b;
graph[a].pb(b);
}
cycle=0;
_init(vis);
fo(i,1,n+1){
if(vis[i]==-1){
dfs(i);
}
if(cycle)break;
}
if(cycle){
cout<<"IMPOSSIBLE"<<endl;
}
else{
reverse(all(top));
cout<<top<<endl;
}
return 0;
}
16) Longest flight routes
I solved this problem using dp. Here there is no cycle so there could not be an infinite path.
What we can do if there is a path like A->B . we find maxpath
for a by just adding 1 to max path of b. dp[a]=max(dp[a],dp[b]+1)
int dfs(int p){
vis[p]=1;
int x;
if(p==n){wt[p]=0;vis[p]=2;return 0;}
for(int aa:graph[p]){
if(vis[aa]==-1){
dfs(aa);
}
if(wt[aa]==-1)continue;
if(wt[aa]+1>wt[p]){
//cout<<p<<" "<<aa<<" "<<wt[aa]<<" "<<wt[p]<<" ";
wt[p]=wt[aa]+1;
to[p]=aa;
// cout<<wt[p]<<endl;
}
}
vis[p]=2;
return wt[p];
}
17) Game Routes
this question is about dp on graph.the number of ways
by which a node A can reach N is equal to sum of ways of its childs.
for(int child:graph[a])dp[a]=(dp[a]+dp[child])%MOD
int dfs(int p){
vis[p]=1;
int x;
if(p==n){wt[p]=1;vis[p]=2;return 0;}
for(int aa:graph[p]){
if(vis[aa]==-1){
dfs(aa);
}
wt[p]+=wt[aa];
wt[p]%=MOD;
}
vis[p]=2;
return wt[p];
}
18) Investigation
The question is basically dijkstra + dp.
You have to run dijkstra and keep track of minimum distance from 1 of all vertex.
If a child has minimum distance = current dis+ edge.weight you just updated the dp.
If a child has min dis>current dis+ edge.weight you reset everyting in dp.
signed main()
{
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int i,j,x;
cin>>n>>m;
int a,b,c;
fo(i,0,m){
cin>>a>>b>>c;
graph[a].pb({b,c});
}
_init(vis);
_init(min_price);
_init0(routes);
_init(min_flight);
_init(max_flight);
_init(can_reachn);
min_price[1]=0;
routes[1]=1;
min_flight[1]=0;
max_flight[1]=0;
priority_queue<pii,vii,greater<pii>> q;
q.push({0,1});
while(!q.empty()){
x=q.top().y;
q.pop();
if(vis[x]!=-1)continue;
vis[x]=1;
for(pii aa:graph[x]){
if(vis[aa.x]==1)continue;
if(min_price[aa.x]==-1||min_price[aa.x]>min_price[x]+aa.y){
min_price[aa.x]=min_price[x]+aa.y;
routes[aa.x]=routes[x];
min_flight[aa.x]=min_flight[x]+1;
max_flight[aa.x]=max_flight[x]+1;
q.push({min_price[aa.x],aa.x});
}
else if(min_price[aa.x]==min_price[x]+aa.y){
routes[aa.x]+=routes[x];
routes[aa.x]%=MOD;
min_flight[aa.x]=min(min_flight[aa.x],min_flight[x]+1);
max_flight[aa.x]=max(max_flight[aa.x],max_flight[x]+1);
q.push({min_price[aa.x],aa.x});
}
}
}
cout<<min_price[n]<<" "<<routes[n]<<" "<<min_flight[n]<<" "<<max_flight[n]<<endl;
return 0;
}
19) Planet queries I
basically tunnel is directed edge and left end is parent and right end is first order child(its direct child).
moving k steps in tunnel means you have to go to kth order child .you can do this using binary lifting.
here is short explanation of binary lifting.
basically we keep tack of all the childs of a node which is at a distance which is power of 2.
if a graph is like this a->b->c->d->e
then first order child of a is b (1st child)
second order child of a is c (2nd child)
and third order child of a is e(4th child)
so by doing this we can find the kth child in log n time .
more about it.
binary lifting cp algo
binary lifting algo live
cin>>n>>q;
fo(i,1,n+1){
cin>>x;
dp[0][i]=x;
}
fo(i,1,LOGN){
fo(j,1,n+1){
dp[i][j]=dp[i-1][dp[i-1][j]];
//cout<<dp[i-1][j]<<" ";
}
// cout<<endl;
}
fo(i,0,q){
int a,b;
cin>>a>>b;
rfo(j,30,0){
//cout<<(b&(1ll<<j))<<" ";
if((b&(1ll<<j))>0){
a=dp[j][a];
}
}
cout<<a<<endl;
}
other useful links
Hope this is helpfull to you . I will try to add more as I solve furthure.
