USACO newbarn

Правка en1, от dx24816, 2018-09-07 04:37:32

Hello,

Can somebody help me debug my code for USACO newbarn (http://www.usaco.org/index.php?page=viewproblem2&cpid=817)? I am in dire need of help, as I have been debugging for around a week. I have no idea why my program is wrong, as every test case I give it, it gives me the right answer. I eventually gave up and just used the USACO test cases, but I it only gets the wrong answer by like line 1000, everything before is right. My strategy is as follows: I use DSU to find the components of all of the barns, and then put all the barns in each component into the forest vector. To calculate the maximum distance, I arbitrarily root each tree in forest, and DFS to precompute the depths of each node. Let a node x be in the subtree of a neighbor n of the root r. The maximum distance to another node is the maximum depth of any node in the subtrees of the neighbors of r (excluding the subtree that n and x are in), or it is the depth of x, or it is the maximum depth of any node in the subtree of n minus the depth of x. I reorder nodes using the seg map making sure nodes in the same component are consecutive, and put them into a segment tree. The bounds vector stores the left most and right most node in each component in the segment tree. Then for each query, I compute the maximum diameter, or update. Can somebody please find my error? Also, I am in need of debugging tips, as I often have the right idea, but can't implement it correctly. If you have any questions at all about my code, just ask. Thanks!

Code (https://ideone.com/oyX7GA)

  • dx24816

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский dx24816 2018-09-07 04:51:56 198
en1 Английский dx24816 2018-09-07 04:37:32 1582 Initial revision (published)