Hello Codeforces Community, I was recently trying to solve this problem on CSES
Following is my approach and code. Approach — Find LCA using Binary Lifting and then compute distance of a to b by doing the following depth[a] + depth[b] — 2 * depth[lca(a, b)].
But I am continuously getting TLE on test 6 and 7(this is not a meme, I am really having difficulty). Can someone help me with what exactly the issue is out here? Is it some large constant factor or smth else. Any help is appreciated.
I remember also getting time limit on this problem, which was fixed by switching the indexing of my binary lifting array for better cache efficiency. I can't look up my old solution right now, but maybe swapping your binary lifting indexing from
[vertex][height]to[height][vertex]helps.Thank you so much!! It worked, but I wonder why is it particularly fast?
vector<vector<int>> binl(n, vector<int>(LOG));The above line is the issue. Change the position of the vector, it would faster ur code. While Allocating 2d vector or 2d array, make the 1st array size to be of smaller size than the second. For ur case, LOG is smaller so it should be the first array size and the vector declaration should be like this -> .
vector<vector<int>> binl(LOG, vector<int>(n));Thank you, just a quick question
As far as I know and understood from attending computer architecture classes, it is due to 2 fact mainly ->1) More Memory Overhead and 2) More Cache Miss.
In ur case, u r creating a lot of vectors(worst case 200000 or so) but of minimum size(LOG), all of the vectors are scattered around in your computer RAM in different locations so accessing them randomly causes a lot of Cache Miss. But, while creating vector -> if u declare LOG at first, u r creating vectors only LOG times which reduces a lot of cache miss while accessing them randomly.
Thank u helped a lot XD:
this might work https://cses.fi/paste/ed06a14e2417edb1f48fbd/
Thanks!!
Must've been the i3-7100U
...Did you know there's a linear time solution?
A simple, $$$O(n\alpha(n))$$$ solution can be found here: https://cp-algorithms.com/graph/lca_tarjan.html
Thank you, will look into it
Auto comment: topic has been updated by luminarae (previous revision, new revision, compare).