Description

Notice: Please use C++11 or above to submit this problem!

After watching the movie 21, Kuo is curious about casino.

There is a casino which opens N days in this month.

There will be two kind of events in a day.

1. Guest <Someone> <Money> <Skill>. It means <Someone> enter the casino with <Money> money. <Someone> are their names, <Money> is the amount of money with them, and <Skill> is how well they play. If <Someone> are already in the casino or are blacklisted, ignore this event.
2. Win <Someone> <Money>. It means <Someone> win <Money> money in a play from the casino. <Money> may be positive or negative. If <Someone> are not in the casino or are blacklisted, ignore this event.

Whenever someone enter the casino, they have to pay T entrance fee to the casino. The enterance fee may change every day.

Whenever one become bankrupt, they will be kicked out of the casino and be blacklisted.

If the amout of money someone win in a play exceed (that is, >) twice of their <Skill>, they will be seen as cheaters, kicked out of the casino, and blacklisted. (The casino still has to pay the money they win to them.)

Someone blacklisted are not permitted to enter the casino. In particular, when someone blacklisted wants to enter the casino, they won't be charged the enterance fee.

Note: If someone have to pay X money but they only have Y money where Y <= X, they will only pay Y money and become bankrupt.

At the end of each day, everyone will leave the casino.

Please help Kuo-chan find how much income the casino gets in this month and who are blacklisted.

Input

The first line of the input contains a number N — the number of days in this month.

The following contains N blocks.

The first line of each block is Casino Q T — it means there will be Q events and the entrance fee is T this day.

The next Q lines is one of the following:

1. Guest <Someone> <Money> <Skill>
2. Win <Someone> <Money>

N <= 1000, Q <= 100. 

There will be at most 1000 different people come to the casino; that is, there are at most 1000 people with different names. Therefore, there will be at most 1000 people blacklisted.

All number is within the range of int.

Output

You should print a number U in the first line — how much income the casino gets in this month.

If there are K people blacklisted in this month, you should output their names in K lines in the order they get blacklisted.

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss

Description

Kuo-chan is given a sequence A and a constant K as his birthday present from Yang-chan.

Kuo-chan is allowed to perfrom the following operation:

1. push x — push x to the tail of A
2. pop — remove the median value of A （the median value of A is A[ (|A|+1)/2 ], with index start at 1）
3. programming tanoshi — for every element a in A, assign a % K to a
4. reverse — reverse the whole A, the head becomes the tail and the tail becomes the head

Whenever performing pop operation, the length of A is guaranteed to be odd, hence A won't be empty.

For example, if A = [4, 3, 5], K = 2

push 11　►　A = [4, 3, 5, 11]

reverse ► A = [11, 5, 3, 4]

push 7　►　A = [11, 5, 3, 4, 7]

pop　►　A = [11, 5, 4, 7]

programming tanoshi　►　A = [1, 1, 0, 1] 

Yang-chan is curious about what A is after Kuo-chan performs some operations to it.

Help him find it out!

（Remember to include function.h in your function.cpp file.）

Input

The first line contains three integers N K Q — the length of A, the constant Yang-chan gives Kuo-chan, the number of operations Kuo-chan performs.

The second line contains N integers a₁, a₂, ..., a_N （1 <= a_i <= N） — the elements of A. 

Each of the next Q lines describes the operations. Each line is one of three types:

1. push x （1 <= x <= 10000）
2. pop
3. programming tanoshi
4. reverse

Different testcases have different constraints.

1. N <= 10³, Q <= 2N, K <= 4000, operations: {pop, push}
2. N <= 10³, Q <= 2N, K <= 4000, operations: {pop, push, programming tanoshi}
3. N <= 10⁵, Q <= 2N, K <= 4000, operations: {pop, push}
4. N <= 10⁵, Q <= 2N, K <= 4000, operations: {pop, push, programming tanoshi}
5. N <= 10⁵, Q <= 3N, K <= 4000, operations: {pop, push, programming tanoshi, reverse}
6. N <= 10⁵, Q <= 3N, K <= 4000, operations: {pop, push, programming tanoshi, reverse}

Output

You should print one line containing the elements of A after the operations. For 1 <= i <= |A|, the i-th number should be A[ i ].

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss

Description

The Traveling Salesman Problem (TSP) is a classical problem that we are to find the shortest distance traversing all vertices in a graph from any source and returning to the source, which is considered hard for computers (and maybe human as well).

Nevertheless, the TSP on tree is quite easy: the shortest circuit must visit all edges exactly twice. You could prove this by induction. So let's consider the Open Loop TSP, in which the salesman is not required to return to the source. 

In this problem, your task is the Open Loop TSP on trees, i.e., finding the shortest distance traversing all nodes in a tree from any source without returning to the source.

Input

There's an interger \(n\) in the first line, indicating the number of nodes in the tree.

The next \(n-1\) lines consist of three integers \(a_i,b_i,w_i\) representing that there's an bidirected edge between \(a_i\) and \(b_i\) weighing \(w_i<2^{31}\).

For \(50\%\) of the testcases, \(n\leq5\times10^4\). For the other \(50\%\) of the testcases, \(n\leq10^6\).

Output

Please print the shortest distance traversing all nodes in a tree from any source without returning to the source.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Procat (破貓) has a lot of electrical appliances in his dormitory, such as computer, refrigerator, and electric fan. He wants to connect all the appliances to the power outlet. There is only one power outlet in his dormitory, so he needs to use extension cords and power strips to connect all the appliances to the power outlet.

Extension cords and power strips Procat currently using don't have overcurrent protection. As a friend of Procat, you are very concerned about electrical safety. You want to help Procat to connect all the appliances to the power outlet in a safe way. Luckily, you have some spare power strips with overcurrent protection. But you don't have any spare extension cords.

Power strips you have got one input and two outputs. Power strips can connect to extension cords, but power strips cannot directly connected to each other.

The price of the high-quality extension cord you want to buy is proportional to the current flowing through it. You wants to minimize the total price of the extension cords you needs to buy.

Calculate total price of the extension cords you need to connect all the appliances to the power outlet.

• After connecting all the appliances to the power outlet, it should look like a binary tree. The power outlet is the root of the tree, and the appliances are the leaves of the tree. The power strips are the internal nodes of the tree. The extension cords are the edges of the tree.

Sample

Following figures show examples of optimal ways to connect the appliances to the power outlet in each sample testcase. In each figure, squares represent power strips, circles represent appliances, and edges represent extension cords. The total price of the extension cords is the sum of current flowing through all the edges.

Sample testcase 1:

Sample testcase 2:

• Hint: Huffman Coding

Input

First line contains an integer \(N\), the number of electrical appliances Procat wants to connect to the power outlet.

The second line contains \(N\) integers \(a_1, a_2, \dots, a_N\), the power consumption of the \(N\) electrical appliances.

\(N\)
\(a_1 \quad a_2 \quad \dots \quad a_N\)

Constraints

• \(1 \leq N \leq 10^4\)
• \(1 \leq a_i \leq 10^9\)

Output

Output contains one line, the minimum total price of the extension cords Procat needs to buy. You don't need to output a newline at the end of the output.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

You signed up for an escape room experience, but something feels off.

The facility has $N$ rooms, numbered $1$ through $N$. Each room has a single door that leads to exactly one other room — or directly outside. You start from room $1$ and follow the doors one by one.

Twenty minutes in, your partner grabs your arm. "We've walked through this room before."

She's right. Somewhere in the layout, an exit circles back. If that loop exists, you're going to keep walking the same stretch of hallway forever. The first room you step into for the second time is where the loop begins.

Given the exit map, find that room. If the path eventually leads outside, output the number of the last room you pass through before the exit.

Implement the following function:

Node *detectCycle(Node *head);

The Node struct is defined in function.h:

typedef struct Node {
    struct Node *next;
} Node;

head points to room $1$. Return the node where the loop begins, or the last node before the exit if no loop exists.

Hint: Compare pointers directly — do not attempt to store or index nodes by values of any kind. Any solution that allocates auxiliary storage proportional to $N$ will exceed the memory limit on the large test cases.

Input

The first line contains an integer $N$.

The following $N$ lines: the $i$-th line contains a single integer $\text{nxt}[i]$ — the room that room $i$'s door leads to. $\text{nxt}[i] = 0$ means the door exits the facility.

Constraints

• Subtask 1, 2: $1 \le N \le 20$
• Subtask 3, 4: $1 \le N \le 10^3$
• Subtask 5~8: $1 \le N \le 10^6$
• $0 \le \text{nxt}[i] \le N$

Output

If a loop exists, output the room number where it begins (the first room visited twice).

If no loop exists, output the number of the last room visited before the exit.

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss

Description

As the chief dispatcher, you are responsible for managing trains across multiple platforms. A train is essentially a sequence of train cars, each with a unique ID.

There are $M$ platforms in the station, numbered from $1$ to $M$. Initially, all platforms are empty. You will receive $Q$ operations, each belonging to one of the following five types:

• ENTER p c: A newly manufactured train car with a unique ID $c$ arrives at platform $p$. It is attached to the very end (tail) of the current train on that platform.
• MERGE p_src p_dest: The entire train on platform $p_{src}$ is moved and attached to the end of the train on platform $p_{dest}$. After this operation, platform $p_{src}$ becomes empty. If $p_{src}$ is empty before this operation, do nothing.
• SPLIT p_src c p_dest: Locate car $c$ which is currently somewhere on platform $p_{src}$. The train is decoupled just before car $c$. Car $c$ and all cars that were behind it are moved to the empty platform $p_{dest}$. The cars in front of $c$ remain on platform $p_{src}$.
• REVERSE p: Reverse the order of all cars of the train on platform $p$.
• CHECK p c k: Starting from car $c$ on platform $p$, move $k$ cars towards the front of the train. Output the ID of the car you reach. If you reach the very first car of the train before taking $k$ steps, stop and output the ID of the first car.

Hint

During peak hours, thousands of cars need to be reassigned every minute.

To prevent severe system bottlenecks, your dispatching system must be highly optimized.

Think about how to find a specific car in $O(1)$ time to perform the SPLIT and CHECK operations efficiently.

Input

The first line contains two integers $M$ and $Q$, representing the total number of platforms and the number of operations.

The following $Q$ lines each contain a command in the format described above.

It is guaranteed that:

• For ENTER, the car ID $c$ has never appeared before.
• For MERGE and SPLIT, $p_{src}$ and $p_{dest}$ are different ($p_{src} \neq p_{dest}$).
• For SPLIT and CHECK, car $c$ is guaranteed to exist on platform $p$ (or $p_{src}$).
• For SPLIT, platform $p_{dest}$ is guaranteed to be empty before the operation.

Constraints

• $1 \le M \le 100,000$
• $1 \le Q \le 200,000$
• $1 \le p, p_{src}, p_{dest} \le M$
• $1 \le c \le 1,000,000$
• $0 \le k \le 100,000$
• The sum of the lengths of the trains reversed across all REVERSE operations will not exceed $5 \times 10^5$.

Subtasks

• Testcases 1: only ENTER and MERGE
• Testcases 2: only ENTER and SPLIT
• Testcases 3: only ENTER and REVERSE
• Testcases 4: only ENTER and CHECK
• Testcases 1-6: $c \le 100$.
• Testcases 7-8: No additional constraints.

Output

1. For each CHECK operation, output the resulting car ID on a new line.
2. After processing all $Q$ operations, output the final sequence of train cars on each non-empty platform.
   • For each non-empty platform from $1$ to $M$, output a line starting with the platform number, followed by a colon : and a space, and then the IDs of the cars on that platform in order from front to end, separated by a single space.
   • If a platform is completely empty, do not output anything for that platform.

Note for Sample I/O

1. ENTER 1 10: Platform 1 has [10].
2. ENTER 1 20: Platform 1 has [10, 20].
3. ENTER 2 30: Platform 2 has [30].
4. MERGE 2 1: Platform 1 has [10, 20, 30], Platform 2 is empty. (Source=2, Dest=1)
5. CHECK 1 30 1: Start at 30, move 1 step towards the front -> reaches 20. Output 20.
6. CHECK 1 30 5: Start at 30, moving 5 steps to the front exceeds the train length, so it stops at the head. Output 10.
7. REVERSE 1: Platform 1 has [30, 20, 10].
8. CHECK 1 10 2: Start at 10, move 2 steps towards the front -> reaches 30. Output 30.
9. ENTER 3 40: Platform 3 has [40].
10. SPLIT 1 20 2: Train on Platform 1 is split before 20. Platform 1 becomes [30], Platform 2 becomes [20, 10].
11. MERGE 3 2: Platform 2 becomes [20, 10, 40], Platform 3 is empty. (Source=3, Dest=2)

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss