Hey guys... ↵
↵
Recently I was solving this [problem](https://cses.fi/problemset/task/1160/) from CSES.↵
↵
Here is what I have tried...↵
↵
<spoiler summary="My idea">↵
↵
Firsly ,↵
↵
- I am finding all cycles in graph↵
- For all nodes , keeping track of in which cycle it belongs to and what is the node no. in that cycle for that node.↵
- erasing all cycle causing edges↵
- then applying binary lifting on inverted tree.↵
↵
--------------↵
↵
now ready to answer queries.↵
↵
- if given starting node is involved any cycle then ending node should also be in same cycle. otherwise ans is -1.↵
↵
If both are in same cycle then we can compute distance between them in O(1) using node nos. of both node.↵
↵
- Now , if Starting node is not in any cycle.↵
↵
Then ending node must be ancestor of it otherwise ans is -1 (not reachable)↵
↵
Now as ending node is ancestor of starting node (talking in inverted tree) , we can walk upto that node ↵
and compute desired no. of jumps.↵
↵
It will be in O(logn).↵
↵
↵
</spoiler>↵
↵
↵
↵
By implementing this idea , I am getting WA in one TC ( Out of 11 ). ↵
↵
You can find my code here.↵
↵
<spoiler summary="code">↵
↵
~~~~~↵
#include<bits/stdc++.h>↵
#define maxn 300005↵
#define ll long long int↵
using namespace std;↵
↵
// https://cses.fi/problemset/task/1160/↵
↵
set<int> par[maxn];↵
vector<int> nxt(maxn);↵
vector<int> kai_cyc(maxn,-1),kyo_node(maxn,-1);↵
↵
vector<bool> v1(maxn,false),v2(maxn,false);↵
vector<vector<int>> cycle;↵
vector<int> tmp;↵
int cyc_id=0;↵
int nn=0;↵
int start=-1;↵
↵
vector<int> tin(maxn),tout(maxn);↵
int tem=0;↵
vector<int> latkav;↵
↵
void dfs(int n)↵
{↵
v1[n]=true;↵
int c=nxt[n];↵
if(v1[c] && !v2[c])↵
{↵
nxt[n]=-1;↵
par[c].erase(n);↵
latkav.push_back(n);↵
start=c;↵
}↵
if(!v1[c]) dfs(c);↵
↵
if(start!=-1)↵
{↵
tmp.push_back(n);↵
kai_cyc[n]=cyc_id;↵
kyo_node[n]=nn++;↵
if(n==start) ↵
{↵
cycle.push_back(tmp);↵
start=-1;↵
tmp.clear();↵
nn=0;↵
cyc_id++;↵
}↵
}↵
v2[n]=true;↵
}↵
↵
vector<vector<int>> up;↵
int mxh;↵
↵
void dfs1(int n,int p)↵
{↵
tin[n]=tem++;↵
↵
up[n][0]=p;↵
for(int i=1;i<=mxh;i++)↵
{↵
if(up[n][i-1]!=-1) { up[n][i]=up[up[n][i-1]][i-1]; }↵
}↵
↵
for(int c:par[n]) dfs1(c,n);↵
tout[n]=tem++;↵
}↵
↵
bool isanc(int u,int v)↵
{↵
return (tin[u]<=tin[v] && tout[u]>=tout[v]);↵
}↵
↵
int main()↵
{↵
jaldi↵
↵
int n,q;↵
cin>>n>>q;↵
for(int i=1,x;i<=n;i++)↵
{↵
cin>>x;↵
nxt[i]=x;↵
par[x].insert(i);↵
}↵
for(int i=1;i<=n;i++)↵
{↵
if(!v1[i]) dfs(i);↵
}↵
↵
//for(vector<int> v:cycle) { deb(v); } //if in same cycle then o(1) ans, else binary lifting↵
↵
mxh=ceil(log2(n));↵
up.assign(n+1,vector<int>(mxh+1,-1));↵
↵
for(int x:latkav) dfs1(x,-1);↵
↵
while(q--)↵
{↵
int start,end;↵
cin>>start>>end;↵
↵
if(start==end) { cout<<"0\n"; continue; }↵
↵
if(kai_cyc[start]!=-1)↵
{↵
if(kai_cyc[start]==kai_cyc[end]) ↵
{↵
int s=kyo_node[start];↵
int e=kyo_node[end];↵
int sz=cycle[kai_cyc[start]].size();↵
cout<<(s-e+sz)%sz<<"\n"; ↵
}↵
else { cout<<"-1\n"; }↵
continue;↵
}↵
if(isanc(end,start))↵
{↵
int jump=0;↵
for(int i=mxh;i>=0;i--)↵
{↵
if(up[start][i]!=-1 && !isanc(up[start][i],end)) { start=up[start][i]; jump+=1<<i; }↵
}↵
cout<<jump+1<<"\n";↵
}↵
else { cout<<"-1\n"; }↵
}↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
So , can someone point out what am I doing wrong or any cases that I am missing.↵
↵
Thanks in advance :)↵
↵
----------------------------------------------------------------------------------↵
↵
**UPD**↵
↵
As [user:pwild,2020-06-25] sir pointed out , I was missing that cases.↵
↵
To overcome that , I just added small logic to my code and it got ACCEPTED.↵
↵
If you want to see code...↵
↵
↵
<spoiler summary="accepted code">↵
↵
↵
~~~~~↵
#include<bits/stdc++.h>↵
↵
#define maxn 200005↵
#define ll long long int↵
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);↵
↵
using namespace std;↵
↵
// https://cses.fi/problemset/task/1160/↵
↵
set<int> par[maxn];↵
vector<int> nxt(maxn);↵
vector<int> kai_cyc(maxn,-1),kyo_node(maxn,-1);↵
↵
vector<bool> v1(maxn,false),v2(maxn,false);↵
vector<vector<int>> cycle;↵
vector<int> tmp;↵
int cyc_id=0;↵
int nn=0;↵
int start=-1;↵
↵
vector<int> tin(maxn),tout(maxn);↵
int tem=0;↵
vector<int> latkav;↵
↵
void dfs(int n)↵
{↵
v1[n]=true;↵
int c=nxt[n];↵
if(v1[c] && !v2[c])↵
{↵
par[c].erase(n);↵
latkav.push_back(n);↵
start=c;↵
}↵
if(!v1[c]) dfs(c);↵
↵
if(start!=-1)↵
{↵
tmp.push_back(n);↵
kai_cyc[n]=cyc_id;↵
kyo_node[n]=nn++;↵
if(n==start) ↵
{↵
cycle.push_back(tmp);↵
start=-1;↵
tmp.clear();↵
nn=0;↵
cyc_id++;↵
}↵
}↵
v2[n]=true;↵
}↵
↵
vector<vector<int>> up;↵
int mxh;↵
↵
void dfs1(int n,int p)↵
{↵
tin[n]=tem++;↵
↵
up[n][0]=p;↵
for(int i=1;i<=mxh;i++)↵
{↵
if(up[n][i-1]!=-1) { up[n][i]=up[up[n][i-1]][i-1]; }↵
}↵
↵
for(int c:par[n]) dfs1(c,n);↵
tout[n]=tem++;↵
}↵
↵
bool isanc(int u,int v)↵
{↵
return (tin[u]<=tin[v] && tout[u]>=tout[v]);↵
}↵
↵
int main()↵
{↵
fastio↵
↵
int n,q;↵
cin>>n>>q;↵
for(int i=1,x;i<=n;i++)↵
{↵
cin>>x;↵
nxt[i]=x;↵
par[x].insert(i);↵
}↵
for(int i=1;i<=n;i++)↵
{↵
if(!v1[i]) dfs(i);↵
}↵
↵
mxh=ceil(log2(n));↵
up.assign(n+1,vector<int>(mxh+1,-1));↵
↵
for(int x:latkav) dfs1(x,-1);↵
↵
while(q--)↵
{↵
int start,end;↵
cin>>start>>end;↵
↵
if(start==end) { cout<<"0\n"; continue; }↵
↵
if(kai_cyc[start]!=-1)↵
{↵
if(kai_cyc[start]==kai_cyc[end]) ↵
{↵
int s=kyo_node[start];↵
int e=kyo_node[end];↵
int sz=cycle[kai_cyc[start]].size();↵
cout<<(s-e+sz)%sz<<"\n"; ↵
}↵
else { cout<<"-1\n"; }↵
continue;↵
}↵
if(isanc(end,start))↵
{↵
int jump=0;↵
for(int i=mxh;i>=0;i--)↵
{↵
if(up[start][i]!=-1 && !isanc(up[start][i],end)) { start=up[start][i]; jump+=1<<i; }↵
}↵
cout<<jump+1<<"\n";↵
}↵
else↵
{↵
int jump=0;↵
for(int i=mxh;i>=0;i--)↵
{↵
if(up[start][i]!=-1) { start=up[start][i]; jump+=1<<i;}↵
}↵
if(kai_cyc[start]==kai_cyc[end])↵
{↵
int s=kyo_node[start];↵
int e=kyo_node[end];↵
int sz=cycle[kai_cyc[start]].size();↵
cout<<((s-e+sz)%sz+jump)<<"\n"; ↵
}↵
else { cout<<"-1\n"; }↵
}↵
}↵
return 0;↵
}↵
↵
~~~~~↵
↵
</spoiler>↵
↵
↵
↵
↵
Recently I was solving this [problem](https://cses.fi/problemset/task/1160/) from CSES.↵
↵
Here is what I have tried...↵
↵
<spoiler summary="My idea">↵
↵
Firsly ,↵
↵
- I am finding all cycles in graph↵
- For all nodes , keeping track of in which cycle it belongs to and what is the node no. in that cycle for that node.↵
- erasing all cycle causing edges↵
- then applying binary lifting on inverted tree.↵
↵
--------------↵
↵
now ready to answer queries.↵
↵
- if given starting node is involved any cycle then ending node should also be in same cycle. otherwise ans is -1.↵
↵
If both are in same cycle then we can compute distance between them in O(1) using node nos. of both node.↵
↵
- Now , if Starting node is not in any cycle.↵
↵
Then ending node must be ancestor of it otherwise ans is -1 (not reachable)↵
↵
Now as ending node is ancestor of starting node (talking in inverted tree) , we can walk upto that node ↵
and compute desired no. of jumps.↵
↵
It will be in O(logn).↵
↵
↵
</spoiler>↵
↵
↵
↵
By implementing this idea , I am getting WA in one TC ( Out of 11 ). ↵
↵
You can find my code here.↵
↵
<spoiler summary="code">↵
↵
~~~~~↵
#include<bits/stdc++.h>↵
#define maxn 300005↵
#define ll long long int↵
using namespace std;↵
↵
// https://cses.fi/problemset/task/1160/↵
↵
set<int> par[maxn];↵
vector<int> nxt(maxn);↵
vector<int> kai_cyc(maxn,-1),kyo_node(maxn,-1);↵
↵
vector<bool> v1(maxn,false),v2(maxn,false);↵
vector<vector<int>> cycle;↵
vector<int> tmp;↵
int cyc_id=0;↵
int nn=0;↵
int start=-1;↵
↵
vector<int> tin(maxn),tout(maxn);↵
int tem=0;↵
vector<int> latkav;↵
↵
void dfs(int n)↵
{↵
v1[n]=true;↵
int c=nxt[n];↵
if(v1[c] && !v2[c])↵
{↵
nxt[n]=-1;↵
par[c].erase(n);↵
latkav.push_back(n);↵
start=c;↵
}↵
if(!v1[c]) dfs(c);↵
↵
if(start!=-1)↵
{↵
tmp.push_back(n);↵
kai_cyc[n]=cyc_id;↵
kyo_node[n]=nn++;↵
if(n==start) ↵
{↵
cycle.push_back(tmp);↵
start=-1;↵
tmp.clear();↵
nn=0;↵
cyc_id++;↵
}↵
}↵
v2[n]=true;↵
}↵
↵
vector<vector<int>> up;↵
int mxh;↵
↵
void dfs1(int n,int p)↵
{↵
tin[n]=tem++;↵
↵
up[n][0]=p;↵
for(int i=1;i<=mxh;i++)↵
{↵
if(up[n][i-1]!=-1) { up[n][i]=up[up[n][i-1]][i-1]; }↵
}↵
↵
for(int c:par[n]) dfs1(c,n);↵
tout[n]=tem++;↵
}↵
↵
bool isanc(int u,int v)↵
{↵
return (tin[u]<=tin[v] && tout[u]>=tout[v]);↵
}↵
↵
int main()↵
{↵
jaldi↵
↵
int n,q;↵
cin>>n>>q;↵
for(int i=1,x;i<=n;i++)↵
{↵
cin>>x;↵
nxt[i]=x;↵
par[x].insert(i);↵
}↵
for(int i=1;i<=n;i++)↵
{↵
if(!v1[i]) dfs(i);↵
}↵
↵
//for(vector<int> v:cycle) { deb(v); } //if in same cycle then o(1) ans, else binary lifting↵
↵
mxh=ceil(log2(n));↵
up.assign(n+1,vector<int>(mxh+1,-1));↵
↵
for(int x:latkav) dfs1(x,-1);↵
↵
while(q--)↵
{↵
int start,end;↵
cin>>start>>end;↵
↵
if(start==end) { cout<<"0\n"; continue; }↵
↵
if(kai_cyc[start]!=-1)↵
{↵
if(kai_cyc[start]==kai_cyc[end]) ↵
{↵
int s=kyo_node[start];↵
int e=kyo_node[end];↵
int sz=cycle[kai_cyc[start]].size();↵
cout<<(s-e+sz)%sz<<"\n"; ↵
}↵
else { cout<<"-1\n"; }↵
continue;↵
}↵
if(isanc(end,start))↵
{↵
int jump=0;↵
for(int i=mxh;i>=0;i--)↵
{↵
if(up[start][i]!=-1 && !isanc(up[start][i],end)) { start=up[start][i]; jump+=1<<i; }↵
}↵
cout<<jump+1<<"\n";↵
}↵
else { cout<<"-1\n"; }↵
}↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
So , can someone point out what am I doing wrong or any cases that I am missing.↵
↵
Thanks in advance :)↵
↵
----------------------------------------------------------------------------------↵
↵
**UPD**↵
↵
As [user:pwild,2020-06-25] sir pointed out , I was missing that cases.↵
↵
To overcome that , I just added small logic to my code and it got ACCEPTED.↵
↵
If you want to see code...↵
↵
↵
<spoiler summary="accepted code">↵
↵
↵
~~~~~↵
#include<bits/stdc++.h>↵
↵
#define maxn 200005↵
#define ll long long int↵
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);↵
↵
using namespace std;↵
↵
// https://cses.fi/problemset/task/1160/↵
↵
set<int> par[maxn];↵
vector<int> nxt(maxn);↵
vector<int> kai_cyc(maxn,-1),kyo_node(maxn,-1);↵
↵
vector<bool> v1(maxn,false),v2(maxn,false);↵
vector<vector<int>> cycle;↵
vector<int> tmp;↵
int cyc_id=0;↵
int nn=0;↵
int start=-1;↵
↵
vector<int> tin(maxn),tout(maxn);↵
int tem=0;↵
vector<int> latkav;↵
↵
void dfs(int n)↵
{↵
v1[n]=true;↵
int c=nxt[n];↵
if(v1[c] && !v2[c])↵
{↵
par[c].erase(n);↵
latkav.push_back(n);↵
start=c;↵
}↵
if(!v1[c]) dfs(c);↵
↵
if(start!=-1)↵
{↵
tmp.push_back(n);↵
kai_cyc[n]=cyc_id;↵
kyo_node[n]=nn++;↵
if(n==start) ↵
{↵
cycle.push_back(tmp);↵
start=-1;↵
tmp.clear();↵
nn=0;↵
cyc_id++;↵
}↵
}↵
v2[n]=true;↵
}↵
↵
vector<vector<int>> up;↵
int mxh;↵
↵
void dfs1(int n,int p)↵
{↵
tin[n]=tem++;↵
↵
up[n][0]=p;↵
for(int i=1;i<=mxh;i++)↵
{↵
if(up[n][i-1]!=-1) { up[n][i]=up[up[n][i-1]][i-1]; }↵
}↵
↵
for(int c:par[n]) dfs1(c,n);↵
tout[n]=tem++;↵
}↵
↵
bool isanc(int u,int v)↵
{↵
return (tin[u]<=tin[v] && tout[u]>=tout[v]);↵
}↵
↵
int main()↵
{↵
fastio↵
↵
int n,q;↵
cin>>n>>q;↵
for(int i=1,x;i<=n;i++)↵
{↵
cin>>x;↵
nxt[i]=x;↵
par[x].insert(i);↵
}↵
for(int i=1;i<=n;i++)↵
{↵
if(!v1[i]) dfs(i);↵
}↵
↵
mxh=ceil(log2(n));↵
up.assign(n+1,vector<int>(mxh+1,-1));↵
↵
for(int x:latkav) dfs1(x,-1);↵
↵
while(q--)↵
{↵
int start,end;↵
cin>>start>>end;↵
↵
if(start==end) { cout<<"0\n"; continue; }↵
↵
if(kai_cyc[start]!=-1)↵
{↵
if(kai_cyc[start]==kai_cyc[end]) ↵
{↵
int s=kyo_node[start];↵
int e=kyo_node[end];↵
int sz=cycle[kai_cyc[start]].size();↵
cout<<(s-e+sz)%sz<<"\n"; ↵
}↵
else { cout<<"-1\n"; }↵
continue;↵
}↵
if(isanc(end,start))↵
{↵
int jump=0;↵
for(int i=mxh;i>=0;i--)↵
{↵
if(up[start][i]!=-1 && !isanc(up[start][i],end)) { start=up[start][i]; jump+=1<<i; }↵
}↵
cout<<jump+1<<"\n";↵
}↵
else↵
{↵
int jump=0;↵
for(int i=mxh;i>=0;i--)↵
{↵
if(up[start][i]!=-1) { start=up[start][i]; jump+=1<<i;}↵
}↵
if(kai_cyc[start]==kai_cyc[end])↵
{↵
int s=kyo_node[start];↵
int e=kyo_node[end];↵
int sz=cycle[kai_cyc[start]].size();↵
cout<<((s-e+sz)%sz+jump)<<"\n"; ↵
}↵
else { cout<<"-1\n"; }↵
}↵
}↵
return 0;↵
}↵
↵
~~~~~↵
↵
</spoiler>↵
↵
↵
↵
