Maria386's blog

Apologies and need help again!
By Maria386, history, 109 minutes ago, In English

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.

  • Vote: I like it
  • +8
  • Vote: I do not like it

»
109 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Maria386 (previous revision, new revision, compare).

→ Reply
»
94 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

figure it out on your own

→ Reply
»
80 minutes ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
77 minutes ago, # |
← Rev. 3   Vote: I like it -8 Vote: I do not like it

shut up why you spam comment section Codeforces is getting TRASHED ALL BECAUSE OF YOU THE FUCK

→ Reply
»
51 minute(s) ago, # |
  Vote: I like it +6 Vote: I do not like it

Doing ans[v].clear() doesn't actually free up the memory used by the vector. Adding ans[v].shrink_to_fit() to free up the memory used by ans[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.

→ Reply
  • »
    »
    27 minutes ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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://codeforces.net/contest/1131/submission/296130011

    → Reply
    • »
      »
      »
      20 minutes ago, # ^ |
      ← Rev. 2   Vote: I like it +3 Vote: I do not like it

      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)$$$.

      → Reply
»
16 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

I changed the line if (-par[v] < -par[u]) to if (par[v]<par[u]) and it worked

You probably meant to write if (-par[v] > -par[u])

→ Reply