Problem C
Conquest of the 7 Seas
Conquering all the world’s seas has always been a grand
dream for any aspiring pirate. However, to achieve this, a
pirate must first form a crew, acquire a ship, and engage in
battles with other pirate crews to emerge victorious. Only the
strongest can conquer the seas! You are a historian on a
spectator ship, and it’s your task to record who is allied with
whom, determine the outcome of battles when two pirate crews
decide to fight, and finally, assess the size of a pirate’s
crew.
Your commander has given you 6 tasks, and at any point will ask
you to do one of the following:
-
Track a new alliance formed between two pirate crews.
-
Confirm if two pirate crews are in an alliance.
-
Track a new pirate crew joining the battle, including their ship size.
-
Provide information about the size of a pirate crew’s alliance.
-
Identify which pirate crews are still in the fight.
-
Report the battle result when two pirate crews fought.
The pirates are in an alliance with their allies’ allies. For example, if Fred the Frog’s pirate crew has an alliance with The Pink Swans, and The Pink Swans formed an alliance with Chonky Cows, Fred the Frog’s pirate crew also has an alliance with Chonky Cows.
Inputs
The first line of input contains an integer $n$ ($5 \leq n < 1 \cdot 10^5$). The next $n$ lines will start with one of the following 6 characters: $u, a, j, s, w, r$. The following are the corresponding inputs for each character:
-
$u$: Two strings $x$ and $y$ will follow. $x$ and $y$ are names of two pirate crews who will join an alliance. It is guaranteed that these two pirate crews are in the fight. It is your task to keep track of this alliance. Note that if $x,y$ are already in an alliance they will just sit down and drink tea, and nothing will happen.
-
$a$: Two strings $x$ and $y$ will follow. $x$ and $y$ are names of two pirate crews. It is guaranteed that these two pirate crews are in the fight. Report to your commander “Aye” if $x$ is in an alliance with $y$, “Nay” otherwise.
-
$j$: A string $x$ and integers $i, k$ will follow. $x$ is the name of the pirate crew joining the battle. $i$ ($1 \leq i \leq 1000$) is the size of the crew, and $k$ ($100 \leq k \leq 1 \cdot 10^4$) is the size of their ship. It is your task to log this crew’s entrance to the battle.
-
$s$: A string $x$ will follow. It is guaranteed that $x$ is already in the fight. Report to your commander the total size of this crew and all of its alliance members.
-
$w$: Nothing will follow. Report to your commander all pirate crews that are still in the fight. This will only ever happen once at the end of the battles.
-
$r$: Two strings $x$ and $y$ will follow. $x$ and $y$ are names of two pirate crews who will be fighting. Its is guaranteed that $x,y$ are in the fight. If a pirate crew is fighting, then every pirate in their alliance will fight as well. The winner is determined by the total size of the pirate crew. Whoever has more pirates will decisively win the fight. If the number of pirates is the same, then it is the total size of their ships. Whoever has the largest total size of ships will win. If they have exactly the same sizes, they both will lose. Pirate crews that lose will leave the battle in shame and never return. Report to your commander which pirate crew won, or if they both lost, or if they’re in the same alliance. Note that only $x$ and $y$ will leave and never return, since they are so ashamed of starting the fight and then loosing. If $x,y$ are in the same alliance, the leaders of both crews will have a diplomatic conversation, and no fighting will happen. In this case neither of them loose or leave the battle.
Note that if $A$ is in an alliance with $B$ and $B$ is in an alliance with $C$, then $A$ is in an alliance with $C$ even if $B$ looses a fight and leave.
All names will not contain any spaces and will only contain characters from the English alphabet in lowercase. All names will be unique. The maximum length for a name will be 6 characters.
Outputs
For each input line starting with $a,s,w,r$ output the following:
$a$: A single “Aye” or “Nay”.
$s$: A single integer, the size of the pirate crew and its alliance.
$w$: The names of the pirate crew still left. Output each name in a line. Order them in alphabetical order.
$r$: The name the pirate crew that won. If both of them lost, output “Arrr, both of them pirate crews be walkin’ the plank!”. If the two crews are in the same alliance output “Ye be a daft one! They be sailin’ under the same flag!”.
| Sample Input 1 | Sample Output 1 |
|---|---|
24 j frog 100 1000 j swan 200 300 j cow 500 500 j toad 500 1000 j bull 100 100 u frog swan u swan cow u toad bull a frog cow a toad frog a toad bull s frog s swan s cow s toad s bull r toad swan r bull cow j hats 800 1800 r swan hats r frog cow j roger 600 500 r frog roger w |
Aye Nay Aye 800 800 800 600 600 swan cow Arrr, both of them pirate crews be walkin' the plank! Ye be a daft one! They be sailin' under the same flag! frog cow frog |
