Hello Everyone I was trying to solve Kth Ancestor problem of HackerRank and I am using binary lifting by storing 2^i th parent of every node u in a 2D dp table p[u][i]. I don’t understand after days of my own research why i am getting wrong answer in 7 Test cases (6,8,9,10,11,12,14). I found a solution almost identical to mine which got accepted he just used transpose of my dp table in his solution. He stored every 2^ith parent of node u in a dp table parent[i][u]. I will be highly grateful if anyone can tell me what is wrong with my code
My code
#include <iostream>
#include <bits/stdc++.h>
#define N 100001
using namespace std;
vector<vector<int>> p(N,vector<int>(18,-1)); //initialized all parents to -1 initially
//Add all 2^i th parents of a node to dp table p
void add(int u, int par){
p[u][0]=par;
for(int j=1; j<18; j++){
p[u][j]=p[p[u][j-1]][j-1];
if(p[u][j] == -1) break; //Ones 2^j th parent becomes -1 (does not exits) all parents above it will also not exist
}
}
//This function deletes all parent of a given node (assign them to -1)
void del(int u){
for(int j=0; j<18; j++){
p[u][j]=-1;
}
}
//Method 1 for finding kth node
//int kParent(int node, int k){
// int curr = node;
// int l=0;
// for(l;(1<<l)<=k;l++); //Finding maximum i so that 2^i is less than or equal to k
// l--;
// for(int i=l; i>=0; i--){
// if((1<<i)<=k){
// curr = p[curr][i];
// k-=(1<<i);
// if(curr==-1) break;
// }
// }
// return curr;
//}
//Method 2 for finding kth parent
int kParent(int node, int k) {
int current = node;
for (int i = 0; i < 18; i++) {
if (((1 << i) & k) != 0) { //Checking ith binary digit of k from left to right is 1 or 0
current = p[current][i]; //If ith binary digit of k is 1 move current to its 2^ith parent
if(current == -1)break;
}
}
return current;
}
int main() {
int t;
scanf("%d",&t);
while (t) {
int p, x, y, q, qt;
scanf("%d",&p);
for (int i = 0; i < p; i++) scanf("%d %d",&x,&y), add(x, y);
scanf("%d",&q);
for (int i = 0; i < q; i++) {
scanf("%d",&qt);
if (qt == 0) {
scanf("%d %d",&x,&y);
add(y, x);
} else if (qt == 1) {
scanf("%d",&x);
del(x);
} else if (qt == 2) {
int k;
scanf("%d %d",&x,&k);
int current = kParent(x,k);
if (current == -1) printf("0\n");
else printf("%d\n", current);
}
}
t--;
}
return 0;
}
Code which is passing all test cases
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int parents[18][100001];
inline void add(int child, int parent) {
parents[0][child] = parent;
for (int i = 1; i < 18; i++) {
parents[i][child] = parents[i - 1][parents[i - 1][child]];
if (parents[i][child] == -1) break;
}
}
inline void remove (int leaf) {
for (int i = 0; i < 18; i++)
parents[i][leaf] = -1;
}
inline int kParent(int node, int k) {
int current = node;
for (int i = 0; i < 18; i++) {
if (((1 << i) & k) != 0) {
current = parents[i][current];
if (current == -1) break;
}
}
return current;
}
int main() {
int tests, n, child, parent, type, node, k;
//cin >> tests;
scanf("%d", &tests);
for (int t = 0; t < tests; t++) {
for (int i = 0; i < 18; i++)
for (int j = 0; j < 100001; j++)
parents[i][j] = -1;
//cin >> n;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
//cin >> child >> parent;
scanf("%d %d", &child, &parent);
add(child, parent);
}
//cin >> n;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
//cin >> type;
scanf("%d", &type);
if (type == 0) { // X Y, Y child of X
//cin >> parent >> child;
scanf("%d %d", &parent, &child);
add(child, parent);
} else if (type == 1) { // node (leaf) remove me
//cin >> node;
scanf("%d", &node);
remove(node);
} else if (type == 2) {
//cin >> node >> k;
scanf("%d %d", &node, &k);
int current = kParent(node, k);
if (current == -1) printf("0\n");
else printf("%d\n", current);
}
}
}
return 0;
}
