The Kingdom's Rebellion

Moderate
0/80
0 upvote
Asked in company
JUSPAY

Problem statement

In the Kingdom of Arborvale, there is a hierarchical system of nobles arranged in a tree-like structure. The kingdom has 'n' nobles, each assigned a unique number from 1 to 'n'. At the top is the King, who is the root of the structure.

Each noble has a parent, except for the King. Some nobles are loyal and respect their ancestors, while others are rebellious.

You are tasked with restoring peace by removing rebellious nobles according to a specific process:

1)You must select a noble to remove who meets all of the following criteria:

I) Is not the King (i.e., is not the root).
II) Is rebellious (does not respect their parent).
III) Has no children who are loyal (i.e., all of its children are also rebellious, or it has no children at all).

2)If multiple nobles meet these criteria, you must select the one with the smallest number.

3)When a noble is removed, all of its children are immediately re-assigned to its parent. This does not affect any other nobles in the current step but may influence future removals.

4)The process continues, selecting and removing one noble at a time, until no nobles are left that meet the removal criteria.

Your task is to determine the order in which the rebellious nobles will be removed.


Detailed explanation ( Input/output format, Notes, Images )
Input Format:
The first line contains an integer 'n', the number of nobles.
The next 'n' lines describe the nobles from 1 to 'n'. The i-th line (for noble i) contains two integers, p_i and c_i:
   I) p_i: The parent of noble i. The King's parent is -1.
   II) c_i: The status of noble i. c_i = 1 if the noble is loyal (respects its parent), and c_i = 0 if the noble is rebellious.


Output Format:
Print a single line containing the space-separated numbers of the nobles in the order they are removed.
If no nobles can be removed, print the word "Peaceful".


Note:
The problem uses 1-based indexing for nobles (from 1 to 'n').
The re-parenting of children after a removal does not happen in the current implementation, as it has been determined that the set of removable nobles is static based on the problem's rules. A noble's condition for removal depends on its own children's loyalty, which does not change throughout the process.
Sample Input 1:
7
-1 1
1 1
1 0
2 1
2 0
3 0
5 0


Sample Output 1:
3 5


Explanation for Sample 1:
The hierarchy is as follows:
- King 1 has children 2 and 3.
- Noble 2 has children 4 and 5.
- Noble 3 has child 6.
- Noble 5 has child 7.

Let's check the nobles who are rebellious (c=0): 3, 5, 6, 7.
Noble 3: Rebellious. Its only child is 6, who is also rebellious. So, 3 has no loyal children. It is a candidate for removal.
Noble 5: Rebellious. Its only child is 7, who is also rebellious. It is a candidate for removal.
Noble 6: Rebellious. It has no children. It is a candidate for removal.
Noble 7: Rebellious. It has no children. It is a candidate for removal.


Sample Input 2:
5
-1 1
1 0
2 1
1 0
4 1


Sample Output 2:
Peaceful


Explanation for Sample 2:
The rebellious nobles are 2 and 4.
Noble 2: Rebellious. However, its child, noble 3, is loyal (c=1). Therefore, noble 2 cannot be removed.
Noble 4: Rebellious. However, its child, noble 5, is loyal (c=1). Therefore, noble 4 cannot be removed.

Since no nobles meet all the criteria, the kingdom is considered "Peaceful".


Expected Time Complexity:
The expected time complexity is O(N log N) due to sorting the candidates.


Constraints:
1 <= n <= 100,000
p_i is -1 or between 1 and n.
c_i is 0 or 1.
The input will always describe a valid tree structure with a single root.

Time limit: 1sec
Approaches (1)
The Kingdom's Rebellion
Time Complexity

The expected time complexity is O(N log N) due to sorting the candidates.

Space Complexity
Code Solution
(100% EXP penalty)
The Kingdom's Rebellion
Full screen
Console