Beautiful Graphs codeforces

I am not able to find the test case on which my this solution https://ideone.com/R4kLkP is getting WA for https://codeforces.com/contest/1093/problem/D Beautiful Graphs question.
I have used the same idea as given in the editorial as well.
Please somebody help i’ve spent almost more than a week on thinking about the wrong testcase and I have no one to ask to.

So you save c++ code as .java ?

1 Like

Oh no sorry i forgot to change the compiler on ideone, i used that just to generate link for my code
I used the cpp compiler only while submitting and running on my system.

On line 141 you should do this cur = (fast_pow(2,p1) %MOD + fast_pow(2,p2)%MOD)%MOD then ans = (ans*(cur%MOD))%MOD.What u did doesn’t make sense.
And I don’t understand why u multiply ans by ansfromfreevert and its not needed .Also whenever a connected component is not bipartite then you should immediately break the dfs and answer would be 0. IMO your code is way too over complicated . You can check my accepted code for reference : https://ideone.com/Be7lRJ .

1 Like

I changed that line and I have put MOD there in this code https://ideone.com/R4kLkP
Also I am returning back when a component is not bipartite ans setting impossible as true and then printing 0 if impossible is true.
I am still getting the same WA on same testcase. Can you please look into it again?

I’m really sorry if my code looks complicated
Right now I am a complete newbie and I have just started to learn how to write short and correct code.

You should just start from 1 to N vertices and do dfs on each vertice that is not visited.That way u do not need to consider vertices that are not in adjacency list. Also using combinatorics you MULTIPLY all the results from each connected components to the answer.So on line 133 u should take a different variable instead of ans and multiply that to the ans.

1 Like

Thanks a lot! Got an AC!
Yes you’re right, by mistake i was reassigning the result of each component instead of multiplying, just changed that and got an AC
thanks a lot for helping!