|
|
back to boardWA 10 I'm searching the farest node for each node via one dfs and then try to answer the query using this information: 1) if(query_dist > distance_to_farest_node_from_query_vertex) output 0 2) if query_vertex is ancestor of it's farest node then i return go_up_from(farest_node_from_query_vertex, dist_to_far_node - query_dist) 3) if dist to lca(query_vertex,farest_node_from_query_vertex) enough (d(lca)>=query_dist) just go up from query_vertex in query_dist steps. 4) if(dist to lca is not enough) then go_up_from( farest_node, farest_node_dist - query_dist) my programm passes my tricky tests,sample test and test from thread. Pls, somebody, give me more tricky tests! Edited by author 10.10.2010 22:43 Re: WA 10 ok, ac now - i count LOG2N variable as floor(log2n) but i should set it ceil(log2n); Re: WA 10 Thanks! I was wondering why I got WA until I saw your reasons. It gave me spirit,now I have got deeper realization of this problem. Edited by author 01.12.2016 19:04 |
|
|