https://www.codechef.com/viewsolution/33604155
this is my solution to Tree diff …similar to editorial approach …
but I am not even able to pass subtask
can anyone please help me and point out what I am doing wrong.
You are not considering the case when there are duplicate values on path say 1 2 4 6 8 2 3
The answer should be 0 but your code will output 1.
for red path your code will give correct ans.
but for blue path your code will ans 1 while ans is 0.
As per your code you should change that set to vector.
Sorry for the bad picture.
1 Like
set contains vertices in the path and not weight on that node
I want to know how are you constructing the path between two nodes when that path contains<=100 nodes???You need to use lowest common ancestor using binary lifting technique
I have depth of each node and parent of each node …so i loop while parent of a and b are not equal
I have depth of each node and parent of each node …so i loop while parent of a and b are not equal
That’s why TLE is coming.I think that’s linear time.Will be ok for 1000 but after that it will give TLE.Use binary lifting
that why i have kept condition s.size>100 return 0 so it won’t process more than 100 nodes
Main Problem with your code is you are not clearing(resetting) all the vectors that you have used before.so for first test case code will work fine. but from 2nd test case on wards dfs will return from node 0 as it was visited in earlier test case.
There is no need of binary lifting. you can get AC without it.
Why TLE?
you are pushing back in all vectors for every new test case.
instead use as follows
like
visited= vector (N,false);
adj.resize(N)
parent=vector (N,-1)
same for parent and level
And best practice is to define the vectors of maximum size and use as you want and don’t forget to reset it like setting to 0 or -1.
like below
const int maxn=2e5+5;
int a[maxn];
vector adj[maxn];
int par[maxn];
int dep[maxn];
and reset for every test case like
for(i,0,n) adj[i].clear()
for(i,0,n) par[i]=-1;
Here is your code I have edited first problem for you.
https://www.codechef.com/viewsolution/33617661
Here is my solution for reference
https://www.codechef.com/viewsolution/33556041
One more thing
add this lines at start in main function
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
it will make code faster.
Thank you very much for pointing out what i am doing wrong …
great explanation and again thanks for your advice