You are not logged in. Please login at www.codechef.com to post your questions!

×

Regarding Lonely Cycles question

I am not able to find a test case where my logic goes wrong... My submission is- My submission

My logic goes as such... For each node x, I find in and out which are pairs... 1st index stores without cycle 2nd stores with cycle...in[x] means within the subtree of node x and also considering x... for this I merge its children's "in" values and also some node in its subtree from which there is back-edge to x.

Out[x] position means same as above...It means the nodes we can visit in the tree except its subtree but including the node itself...for this I merge its parent's out and also it's siblings in...Also in case of back-edge from x to some node higher in the dfs traversal tree, I merge its out...

For answer, consider for edge (a-b)

case (i):(a is dfs_par[b] or vice versa... and not part of same cycle) answer is (in[b])*(merge(out[a], sibling[b]))

case (ii):(neither is parent of other but are part of cycle connected by back-edge)answer is (in[b])*(out[a]) (consider a comes before b in dfs traversal)

This question is marked "community wiki".

asked 13 Aug '18, 21:17

v1a9r9u8n's gravatar image

4★v1a9r9u8n
32
accept rate: 0%

edited 13 Aug '18, 22:15


You've a minor mistake while calculating paths for edges which are near two cycle.

Link to your code : https://ideone.com/8OFIAS with input and expected output, and output of your code. For edge 7-5, the answer is 2 but your code outputs 1.

link

answered 13 Aug '18, 23:51

forgotter's gravatar image

4★forgotter
2025
accept rate: 0%

Still getting WA...that was the error though

(14 Aug '18, 09:51) v1a9r9u8n4★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,424
×196

question asked: 13 Aug '18, 21:17

question was seen: 339 times

last updated: 14 Aug '18, 09:51