Planets Queries II CSES

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	167
2	Um_nik	163
2	maomao90	163
4	atcoder_official	161
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	nor	153
9	Dominater069	153

Hey guys...

Recently I was solving this problem from CSES.

Here is what I have tried...

My idea

By implementing this idea , I am getting WA in one TC ( Out of 11 ).

You can find my code here.

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;
}

So , can someone point out what am I doing wrong or any cases that I am missing.

Thanks in advance :)

UPD

As pwild 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...

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;
}

#include <iostream> #include<map> #include<unordered_map> #include<vector> #include<climits> #include<queue> #include<set> #include<cmath> #include<algorithm> #define pb push_back #define N (lli)(2e5) #define lli long long int #define mod (lli)(1e9+7) #define INF lli_MAX #define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL) using namespace std; // THOR>>>HULK vector<int>p2(N); int ns,ne; void dfs2(int x,vector<vector<int>>&adj,vector<int>&parent,vector<int>&level,vector<int>&cycle,vector<int>&tree) { for(int node : adj[x]) { if(cycle[node]==0) { parent[node] = x; level[node] = level[x]+1; tree[node] = tree[x]; dfs2(node,adj,parent,level,cycle,tree); } } } bool lca_superfast(int u,int v,vector<int>&level,vector<int>&parent,vector<vector<int>>&sparse) { if(u==v) return true; if(level[u]<level[v]) return false; int diff = level[u] - level[v]; while(diff!=0) { int pw = p2[diff]; diff = diff - (1<<pw); u = sparse[u][pw]; } if(u==v) return true; return false; } void dfs(int x,vector<int>&vis,vector<int>&to) // cycle detection { vis[x] = 1; int y = to[x]; if(vis[y]==1) { ns = y; ne = x; } else if(vis[y]==0) dfs(y,vis,to); vis[x] = 2; } int main() { fast_io; int n,q; cin>>n>>q; vector<int>to(n+1); vector<vector<int>>rgr(n+1); for(int i=1;i<=n;i++) { cin>>to[i]; rgr[to[i]].pb(i); // keeps reverse graph } int prev_cycle = 0; // keeps account of current cycle number int cur = 0; // keeps current number of node within a cycle vector<int>cycle(n+1,0); // keeps record of cycle number of a node; vector<int>in_cycle(n+1,0); // keeps number of a cycle node within a cycle vector<int>vis(n+1,0); vector<int>tot(n+1,0); // keeps total number of nodes in a cycle for(int i=1;i<=n;i++) if(!vis[i]) { ns = ne = -1; dfs(i,vis,to); if(ns==-1) continue; prev_cycle++; cur = 0; int t = ns; while(t!=ne) { cycle[t] = prev_cycle; in_cycle[t] = ++cur; t = to[t]; } cycle[t] = prev_cycle; in_cycle[t] = ++cur; t = to[t]; tot[prev_cycle] = cur; } p2[1] = 0; for(int i=2;i<N;i++) p2[i] = p2[i/2] + 1; vector<int>tree(n+1,0); // keeps inverted tree number of the node vector<int>parent(n+1,0); // keeps parent of each node in inverted tree vector<int>level(n+1,0); // keeps level of each node in inverted tree vector<vector<int>>sparse(n+1,vector<int>(31,0)); // keeps super parents of each node for(int i=1;i<=n;i++) { if(cycle[i]) { tree[i] = i; dfs2(i,rgr, parent, level,cycle,tree); } } for(int i=1;i<=n;i++) if(!cycle[i]) sparse[i][0] = parent[i]; for(int j=1;j<31;j++) for(int i=1;i<=n;i++) if(!cycle[i]) sparse[i][j] = sparse[sparse[i][j-1]][j-1]; // for(int i=1;i<=n;i++) // { // for(int j=0;j<5;j++) cout<<sparse[i][j]<<" "; // cout<<endl; // } int a,b; while(q--) { cin>>a>>b; if(cycle[a]==0) { if(cycle[b]==0) { int x1 = tree[a]; int x2 = tree[b]; if(x1!=x2) cout<<-1; else { bool p = lca_superfast(a, b, level, parent, sparse); if(!p) cout<<-1; else cout<<level[a]-level[b]; } } else { int x1 = tree[a]; int c1 = cycle[x1]; int c2 = cycle[b]; if(c1!=c2) cout<<-1; else { int t = tot[c1]; int y1 = in_cycle[x1]; int y2 = in_cycle[b]; if(y2>=y1) cout<<y2-y1+level[a]; else cout<<t-(y1-y2)+level[a]; } } } else { if(cycle[b]==cycle[a]) { int x1 = in_cycle[a]; int x2 = in_cycle[b]; int t = tot[cycle[a]]; if(x2>=x1) cout<<x2-x1; else cout<<t-(x1-x2); } else cout<<-1; } cout<<endl; } }

Comments (3)

Show archived | Write comment?

pwild

4 years ago, # |

I did not check if this is what you actually do in your code, but erasing one edge in every cycle is not correct: a node that is not on the cycle can reach all nodes on the cycle, but for some of them this may require passing over the erased edge.

→ Reply

kgargdun

← Rev. 2 →

I recently stumbled upon this problem. Found this blog helpful. My code (Tried to code as simple as possible)

Here

...

thechamp95821

6 weeks ago, # ^ |

One small doubt, why are we keeping a reverse graph, I cant understand the intuition behind that

Peace_789's blog