Description

Download the C++ reference.
You will see the file named "12534.cpp" but that's OK.
Just download the file and change the filename extension(副檔名) into "zip" then you can upzip the file and use the reference.
The link is below.

reference.zip

Input

Output

Sample Input  Download

Sample Output  Download

Partial Judge Code

12534.cpp

Partial Judge Header

12534.h

Tags

Discuss

Description

In Object-Oriented Programming (OOP), the inheritance among classes represent ``is-a'' relationships for abstractions. Graphs and trees are both fundamental for computer science. In fact, a tree is a special case of a graph that is connected as well as acyclic.

In fact, we often implement trees and graphs by similar means in practice. For instance, we tend to store trees and graphs by adjacent matrice or lists. Moreover, we traverse trees and graphs in alike ways.

For simplicity, we only consider basic operations on trees and graphs. You need implement BFS traversal for a graph starting from a given source and returning the distance to all other vertices so that trees could inherit that method. Furthermore, you should find the diameter (the longest distance in a tree that we've encountered several times but solved by DFS then) by BFS traversal.

Input

Please see the instructions in the header. BFS traversal would be called with the source. As for diameter, there's no parameter.

It's guaranteed that the graph is connected and simple, and that the number of vertices of a tree is less than 100000.

Output

For BFS traversal, you should return a vector of n integers indicating the minimum distance from source.

As for the diameter, you should return an integer.

Sample Input  Download

Sample Output  Download

Partial Judge Code

13879.cpp

Partial Judge Header

13879.h

Tags

Discuss

Description

You find that everybody has already had a black box, but you don't think you have earned enough money, so you decide to invent  a new black box -- "white box". The white box has one more function than the black box -- it can answer you which number has the most in it.

All operations you can do to the white box are as follow:

1. 1 k x: add number x into the box k times 
2. 2 k x: remove number x in the box k times, if number x in box is fewer than k, just remove all x
3. 3 x: ask how many x are in the box
4. 4: ask the maximum number in the box, if there are no number in the box, the box will answer you "The box is empty."
5. 5: ask the minimum number in the box, if there are no number in the box, the box will answer you "The box is empty."
6. 6: ask the most number and its occurences in the box, if there are more than one number has the most occurences, the answer will be the largest one, if there are no number in the box, the box will answer you "The box is empty."

If you want to earn more money(or simply want to pass this course), please make the magical white box. 

Input

The first line contains an integer N -- the number of operations you will do to the black box.

The next N lines will be the operations as above.

1 <= k <= 1e9.

-1e9 <= x <= 1e9.

For testcase 1~3: 1 <= N <= 1e3.

For testcase 4~6: 1 <= N <= 2e5.

Output

For operation 3 ~ 6, please output the corresponding answer.

Sample Input  Download

Sample Output  Download

Tags

Discuss