Hello everyone. last week my teacher set's JOI18_bitaro as my homework (you can see the problem in here). I really tried to solve it and I spend many of hours thinking about it and finally I solved it. I didn't find any blog about its solution so I solve it in this blog.

I really appologize if this blog isn't good enough.

The main idea of this problem's solution looks too easy but actually it's difficult so don't be disappointed if you couldn't solve it.

At first we should solve the subtask 2 (really the first subtask isn't important) and then generalize it's solution for the subtask 3.

The subtask 2 is reaslly easy and we can solve it with only basic dp, but it don't work for subtask 3 because this dp solution takes O(m) time complexity and if q = 100000 then it will be time limit exceeded. Now note that sum of y of any query is not greater than 100000, so if y > sqrt(100000) we can handle the query by dp.

In this part of solving the problem we should just find a way to handle the queries with y less than sqrt(100000) and for doing this we can store a vector or array for any vertex and I name it lps (lengest paths).

Lps of v contains the first sqrt(100000) longest paths ending to v, I mean if for every vertex v we make a vector such that for vertex 1 ≤ u ≤ n, the longest path from u to v is in the lps of v and then we sort the elements in non increasing order and then we pop_back the vector while its size is greater that sqrt(100000).

After doing this we can handle the quries with y less than sqrt(100000), how? we go through the lps of t (vertex of party) and if any vertex in t's lps is removed (every query gives y vertices after giving t and y, I name them removed vertices) I mark it, then I find the maximum of not marked elements in lps of t and it's the answer of this query, why? we have sqrt(100000) vertex in lps of t and y is less that sqrt(100000) so there is at least one not marked vertex v in the t's lps and we know longest path of other vertices out of t's lps isn't greater that longest path of vertex v, so we if we find the maximum of not marked longest paths in t's lps, we found the answer. (if the size of t's lps is less that sqrt(100000) so we don't have sqrt(100000) vertex such that they have a path to t, so if all the vertices in the t's lps marked, the answer will be -1)

You can see my implemantation in here.

Thanks for reading my blog and sorry for my poor english.

I'm waiting to see your usefull comments to improve my next blogs.

Hello everyone. Last week my teacher gived me a problem and told me to solve it using sqrt, but it wasn't easy for me and when I tried to find a solution using sqrt I didn't found any answer and now I want to write a blog of solve 916D using sqrt for next people who want to solve this problem by sqrt.

This blog is my first blog and I appologize if it isn't good enough.

In this problem we should handle five queries:

1- Add a new word to to-do list with a priority.

2- Change priority of a word.

3- Remove a word from to-do list.

4- Find how many words have a priority less than priority of given word.

5- Change the to-do list to its last versions.

The main idea of the solution is that we can decompose the to-do list to blocks with langth at most T and than when we want to make a change in to-do list, we can just make a change in one block; but we in this problem we should save the last versions of to-do list, so we dublicate that block we must change it and now we change the new block (we can maintain the blocks in a vector or array). Also we should save an array of length n/T for each query, that contain indexes of blocks of that version of to-do list, thus for undo query we should just copy the array of target version in new version.

At next we should have two type blocks:

1- A block that contain priorities in not decreasing order (it can be vector or array) so we can find how many priorities are less than given priority for any block with binary search (using lower_bound).

2- A block for find that a word is in the i-th block or not and if it is in i-th block then what is its priority (at first I used unordered_map but it's better with array).

In the next step of solving we should convert the words to integers using unordered_map or map (unordered_map is better) and we should make an unique id for any word, by doing this we can say a word with k * T ≤ id < (k + 1) * T must go to k-th block of each queriy's array of blocks.

For first query in the block of second type we set priority of given word equal to given priority and we add given priority to block of first type using insert method of vector (it take O(T) operations) (if a word's priority is zero in second type block, then it isn't exists).

For second query we change the priority of given word in second type block and we remove the old priority of first type block using erase method of vector and we insert the new priority in that block by insert method of vector (it takes O(T) operations).

For third query we just erase the word's priority from first type block and we set priotity of that word equal to zero in second type block.

For fourth query we go through blocks of first type in array of that version of to-do list and using lower_bound we find number of priorities less than given word's priority in each first type block.

For fiveth query we just copy the target version of to-do list is the new version of to-do list.

You can see my solution code in 225492217.

Thanks for reading my first blog and sorry for my poor english.

I'm waiting to read your usefull comments for my next blogs.