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

×

CLOVER - Editorial

PROBLEM LINKS:

Practice

Setter : Vatsal Gupta

Tester : Shubham Grover

DIFFICULTY:

Medium-Hard

PREREQUISITES:

Depth First Search,Segment Trees

EXPLANATION:

Firstly, here we use the thing that if we dfs a tree and we keep a stack such that

we push a element to the stack when we arrive at it and pop the element from the

stack when we depart from it, therefore when we depart from node x the

elements on the stack are the elements which lie on the path from root to x

(reader’s can easily prove this).

Here we use the same thing, we maintain an array (arr) of the maximum value in

the nodes and each index of this array works like the stack discussed above (i.e.

Suppose a node of value v is arrived we push the arrival time of this node to

arr[v] and next, suppose a node of value v is departed we pop the arrival time of

this node from arr[v]).

Now, all we need is the closest vertex with value greater than some value (x). For

that we have an array (arr2) of the maximum value in the nodes such that arr2[i]

stores the top of the stack at position i in “arr” array described above.

Now,we simply need the maximum value in the range (x,maximum

value in the nodes) which is actually the arrival time of the vertex closest to the

given vertex and has a value greater than the given value,

For this we apply segment tree to find the maximum value in a range and also we

apply point updates in the segment tree every time we arrive or depart a vertex

in the dfs run.

Since we can store the answer for each vertex beforehand in the dfs run we can

simply answer the queries in O(1) by maintaining an array such that the array[i]

stores the answer for the vertex i and update this array during the dfs run.

Total Complexity : O(Nlog(Max value)+Q)

SETTER'S SOLUTION:

Can be found here

asked 11 Oct '16, 12:52

mightysg's gravatar image

2★mightysg
41
accept rate: 0%

edited 02 Jan '17, 18:44

admin's gravatar image

0★admin ♦♦
19.8k350498541


My code is being showed as a wrong answer even though it is getting executed successfully with the sample input . Please tell me where am I making the mistake . Thank you .

https://www.codechef.com/viewsolution/11780190

link

answered 11 Oct '16, 15:00

vj2016's gravatar image

0★vj2016
1
accept rate: 0%

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:

×15,639
×1,755
×1,240
×726
×1

question asked: 11 Oct '16, 12:52

question was seen: 940 times

last updated: 02 Jan '17, 18:44