Only passing 2 test Cases. Help anyone?


my code: https://ideone.com/ErsROj

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

2 Likes

Is it still wrong when you clear the adjacency lists between test cases?

Yes its still failing :frowning:

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

1 Like

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 :sob:

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 ? :point_up_2: , 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

1 Like

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 :slight_smile:

lli LOG2(lli n){
    lli cnt=0;
    while(n){
        cnt++;
        n/=2;
    }
    return cnt;
}

Screenshot_2020-06-24 mereko risk lene ka hi nhi hai - Google Search

2 Likes

:rofl:

Sorry, forgot to reply, but that link doesn’t work: