LCC '18 Contest 5 J5 - Long Live the King!

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 2.0s
Memory limit: 128M

Problem type

In 1701, the British parliament passed the Act of Settlement, which describes the succession of the British monarch.

The algorithm of succession can be described as "the crown" moving to different people.

The rules are as follows:

  1. The crown begins at the current monarch.
  2. The crown moves to the oldest son of the current person, whether dead or alive.
    • If this person has already been visited, move to the next sibling based on the priority of gender and age.
    • If the current person has no sons, the crown moves to the oldest daughter.
    • If at a dead end (no valid children and current person is not alive), move to the parent of the current person and apply rule \(2\) again.
  3. If the current person is alive, they become the monarch. Otherwise, repeat step \(2\).

The British government has asked you to help them determine the next monarch, can you help them?

Input Specification

The first line of input will contain one integer, \(N\ (2 \leq N \leq 10^5)\), the number of people in the family tree.

The next \(N\) lines each contain a description of a person. Line \(a_i\) describes the \(i^{th}\) person.
Each line contains three space separated strings and one integer, in the following order:

  • \(p\), the person's name (the length of which will be less than or equal to \(20\) characters)
  • \(g\), the gender of the person (either male or female)
  • \(s\), whether the person is alive or not (either dead or alive)
  • \(z\), the person's age in minutes \((0 \leq z \leq 10^6)\).

The name and age of any given person is guaranteed to be unique.

The next \(N - 1\) lines each contain space separated strings, \(x\) and \(y\), which describes that person \(x\) has a child named \(y\). It is guaranteed \(x \neq y\).

The next line will contain a string, the current monarch's name.

It is guaranteed the \(N-1\) connections form a valid family tree.

Output Specification

The output will contain a single string, the name of the next monarch. It is guaranteed that one will exist.


Subtask 1 [50%]

\(N \leq 40\)

Subtask 2 [50%]

No further constraints.

Sample Input 1

ShaniyaGorczany female dead 19403
MsAnissaEichmann male alive 12417
LottieErnser female alive 33512
NeomaEmard female alive 82224
ShaniyaGorczany MsAnissaEichmann
ShaniyaGorczany LottieErnser
ShaniyaGorczany NeomaEmard

Sample Output 1


Explanation for Sample 1

The crown favors males, so even though NeomaEmard and LottieErnser are both older, MsAnissaEichmann gets the crown as the oldest living son.

Sample Input 2

MurlGutmannSr male dead 91182
DrMayeThompson female alive 75982
BarneyReilly female alive 92830
AndreCarroll female alive 64179
MurlGutmannSr DrMayeThompson
MurlGutmannSr BarneyReilly
MurlGutmannSr AndreCarroll

Sample Output 2


Explanation for Sample 2

We begin at a dead end (no children), so we back up to MurlGutmannSr and go to the oldest female, BarneyReilly. DrMayeThompson has already been visited so there are no more males that could be chosen.


There are no comments at the moment.