Ok Code Forces
I realize the error in the previous blog is huge and if I knew how to delete the blog I would have done so. Before I reach the poverty line in the Contribution area again.
But I really have a question this time!
I had written this code (296121982) for 113F but finally by converting the vector to a list I managed to solve this problem(296125493).
But I saw a friend who was able to solve the question with the same process(110436429). Can you guide me?
Thank you in advance.
Auto comment: topic has been updated by Maria386 (previous revision, new revision, compare).
Check your merge function (In the first attempt that you got Memory Limit Exceeded). instead of "-par[v] < -par[u]", use "par[u] > par[v]" since your intention is u>v (if im wrong then sorry again :))
That's right. Thank you.
shut up why you spam comment section Codeforces is getting TRASHED ALL BECAUSE OF YOU THE FUCK
Doing
ans[v].clear()doesn't actually free up the memory used by the vector. Addingans[v].shrink_to_fit()to free up the memory used byans[v]makes your MLE submission TLE. This means your vector merging probably isn't optimal. Your friend's submission uses something called small-to-large merging, which you can find good explanations for online.By the way, please ignore the troll comments above. They are just people who have nothing better to do with their time than belittle others.
Um, I think the clear one still work? I can still Accepted this problem using the similar idea? Can you explain for me please?
My attept: https://mirror.codeforces.com/contest/1131/submission/296130011
Here you are also doing small-to-large merging, so the memory complexity is $$$O(n \log n)$$$, which can pass. You merge $$$u$$$ to $$$v$$$ if $$$u$$$ is the representative of less nodes than $$$v$$$. The other submission does the opposite, so its memory complexity is $$$O(n^2)$$$.
Oh thanks! I didn't know I was using it :)
Yes. Thank you very much and I agree with you about the troll comments above.
I changed the line
if (-par[v] < -par[u])toif (par[v]<par[u])and it workedYou probably meant to write
if (-par[v] > -par[u])Oh my god. You're exactly right.