my code: ErsROj - Online C++ Compiler & Debugging Tool - Ideone.com
Are you clearing the adjacency lists between test cases?
No
You probably should
@galencolin i only used one map to keep track of parents, but this method is giving me TLE in half of cases… is there any other way to find out about this ?
If you’re doing it naively, that’s too slow, you need something like binary lifting
Although if you mean doing binary lifting in O(n\log^2{n}) with a map, why? There’s no reason to use a map
Is it still wrong when you clear the adjacency lists between test cases?
Yes its still failing
Seems like with that test case the problem is adding nodes
The best way to debug when you know a test case that’s wrong is to print everything you can and see what deviates from what you expect it to be
hey @galencolin thanks for suggesting binary lifting, it took away TLE.
i tried binary lifting for the first time, i took a while, my code ran fine on the sample test cases but all other test cases failed
sorry i don’t know how to share code from hackerrank, so here it is in raw form… any help would be appreciated.
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <math.h>
using namespace std;
int n,l;
int b_lift [100001][18];
vector<int> Tree[100001];
int depth[100001];
bool nodes[100001];
void dfs (int a, int p) {
depth[a] = depth[p] + 1;
b_lift[a][0] = p;
for (int i = 1 ; i <= l ; i++) {
if ((1 << i) > depth[p]) break;
b_lift[a][i] = b_lift[b_lift[a][i-1]][i-1];
}
for (int i : Tree[a]) {
if (i != p) dfs(i,a);
}
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
int tt ; cin >> tt;
while ( tt-- ) {
for (auto& i : Tree) i.clear();
memset(nodes,0,sizeof(nodes));
cin >> n;
l = log2(n);
int x, y, head;
for (int i = 0 ; i < n ; i++) {
cin >> x >> y;
if ( y == 0 ) { head = x ; continue; }
Tree[x].push_back(y);
Tree[y].push_back(x);
nodes[x] = true;
}
depth[0] = 0;
dfs(head,0);
int q, op, cur ; cin >> q;
for (int i = 0 ; i < q ; i++) {
cin >> op;
if (op == 0) {
cin >> x >> y ;
Tree[x].push_back(y);
Tree[y].push_back(x);
dfs(y,x);
nodes[y] = true;
} else if (op == 1) {
cin >> x ;
nodes[x] = false;
} else {
cin >> x >> y;
if (depth[x] <= y || nodes[x] == false){
cout << 0 << '\n';
continue;
}
cur = x;
for (int k = 0 ; k < 17 ; k++) {
if (y & (1 << k)) {
cur = b_lift[cur][k];
}
}
cout << cur << '\n';
}
}
}
return 0;
}
@galencolin can you help me find why is this code causing problem ? , i can’t find where it is going wrong … except it is producing segmentation fault on larga data input.
in queries, op == 0 is to add a leaf node,
op == 1 is to delete a leaf node.
and op == 2 is to find y-th ancestor of node with value x.
Does memset
with an array of vectors actually work? It seems like it would delete the vector object (as in, set the entire Tree
array to null pointers) and make it segfault when you try to call it later.
Also, it should be dfs
, not bfs
(nitpick).
Also, because you have multitests, you have to reset depth
(or at least, the root) each time.
Also, log2
is dangerous (not sure if it makes a difference here though), it’s probably better to just fix the bit i
you’re looking at and check if y & (1 << i)
is true each time.
Could be more things, fix those first
edit: did i reply to the wrong person? This is for @sirearsh
I’m still not able to find the bug in it? Its terminating in hackerrank ide after first test case,can you please go through my code once.
A nice implementation for log2(n)
is
63 - __builtin_clzll(n)
Don’t you know a case it’s failing on, though?
Hey thankyou, but this didn’t made any change, Somethink is wrong in Query part of the code as program stays fine up till reading nodes, and it randomly shows segmentation fault while running queries. something beyong my knowledge is going in there. can you suggest me a book to study cpp thoroughly?
i updated the code above, here is the test case it is failing on link.
I did this always
lli LOG2(lli n){
lli cnt=0;
while(n){
cnt++;
n/=2;
}
return cnt;
}