I really don't mean to bother anyone, this has just been annoying me for a good amount of time.
The problem is 835G. I seem to have a working solution but it's timing out at test 38.
I thought my solution worked in O(n) but it clearly either doesn't or something else is very wrong. My thought process was that both makeWanted and dfs should work in O(n) since there are no loops in a tree, so solve() should be O(n) as well.
I'd be incredibly thankful if you could have a look and see where I'm wrong :)
It seems that the unordered_set is running in its worst time complexity O(n) instead of O(1) so the algorithm is possibly O(n^2), I reckon a lot of hash collisions. If you just change the unordered set to a normal set instead which would run in O(n log n), it is a lot faster. https://codeforces.net/contest/1760/submission/206029716 . I hope someone smarter can tell you better why it is specifically slower here.
That’s really insightful thanks so much!
There is also a blog about how to use a custom hash for unordered_map so that it wouldn't run in O(n). Here
Auto comment: topic has been updated by fmoeran (previous revision, new revision, compare).
instead of unordered_set you should use set and every time you are creating a new graph you should make an array of vectors globaly of maximum constraints given in the problem statement only once so that it will have a better time complexity and constant memory like if maximum is 10^5 so you should have like vectorgraph[1e5+10] and at every test case you clear it up.And don't forget to define maximum n as constant like int const MAXN=1e5+10;
Yeah the solution was to use set over unordered_set.
Your thing on using a max sized array and clearing it each test case was wrong though. It only makes it constant space by using a stupidly unnecessary amount of memory every time. Also clearing an array takes O(n) since you have to use fill() whilst vector::clear() is O(1) so a 2d vector is slightly better. But none of that matters cause the algorithm itself is O(nlogn).
i was suggesting array because arrays are much faster than vector and takes less space than vectors
Do you have a source that states vector::clear() is O(1)? From what I have read online I thought it was O(N) time complexity.
Oh you’re probably right. The way I imagined it working is it just de-allocates the memory that it was using, which means it doesn’t have to manually set each item to 0, just tell the operating system that other processes can use that memory.
I’m not very good at memory management stuff though so you may be right.