Description

(20 points)

You are given information about a group of employees in a company.
Each employee is represented by the following structure:

typedef struct {
    int id;                 // unique employee ID
    char firstname[32];     // first name
    char lastname[32];      // last name
    int boss_id;            // direct supervisor's employee ID
} employee;

• Each employee has a unique ID (id).

• boss_id stores the direct supervisor’s ID.

• If an employee’s boss_id is the same as their own id, that employee is the top-level boss.

• All employees and their supervisors are guaranteed to appear in the input.

You will receive several queries.
Each query specifies an employee’s full name and an integer k.
Depending on the value of k, you must perform one of the following operations:

k = 1 — Print all of their colleagues

Print all employees who share the same direct supervisor as the queried employee
(excluding the employee themself and excluding the top-level boss).

Example

Query: James Vance 1

Output: Ching-te Lai

k = 2 — Print their supervisors (from nearest to farthest)

Print the chain of supervisors starting from the employee’s direct boss,
then that boss’s boss, and so on, until reaching the top-level boss.

Each supervisor is printed on its own line as:

firstname lastname 

Example

Query: Miku Hatsune 2

Output: James Vance Donald Trump

k = 3 — Print their subordinates (from nearest to farthest)

Print all employees who are under the queried employee in the hierarchy.

• First print all direct subordinates of the queried employee.

• Then, for each of those subordinates, print their subordinates recursively.

• When there are multiple subordinates at the same level, you must always process the one with the smaller index in the input list first.
  In other words, among all employees who have the same boss, visit them in ascending order of their array index (0, 1, 2, …).

Each subordinate is printed on its own line as:

firstname lastname 

Example

Query:
Donald Trump 3

Suppose the input order is:

1. Miku Hatsune

2. James Vance

3. Donald Trump

4. Ching-te Lai

Then the output should be:  James Vance Miku Hatsune Ching-te Lai

Here:

• James Vance and Ching-te Lai are direct subordinates of Donald Trump.

• Miku Hatsune is a subordinate of James Vance.

• Since James Vance has a smaller index than Ching-te Lai, his subtree is printed first:

  • James Vance

  • then his subordinate Miku Hatsune

• Then the subtree of Ching-te Lai (who has no subordinates) is printed.

Hint

For k = 1, two employees are colleagues if they have the same boss_id (and are not the same person). 

For k = 2, starting from the queried employee, repeatedly move to their boss (using boss_id) until you reach the top-level boss.

For k = 3, starting from the queried employee, recursively find all employees whose boss_id matches this employee’s id.

Here is a Pseudo-code for k = 3 condition,

function DFS_Subordinates(employees, n, boss_index):
    for i from 0 to n-1:
        if employees[i].boss_id == employees[boss_index].i and employees[i].id != employees[i].boss_id:
            print employees[i].firstname, employees[i].lastname
            // Recursively process this subordinate
            DFS_Subordinates(employees, n, i)

function print_subordinate(employees, n, employee_index):
    if employee_index < 0:
        return
    DFS_Subordinates(employees, n, employee_index)

Input

• The first line contains an integer n, the number of employees.

• The next n lines each contain four values describing one employee:

id firstname lastname boss_id

• The following line contains an integer m, the number of queries.

• Each of the next m lines contains a query in the form:

firstname lastname k

where firstname lastname identifies the employee being queried, and k specifies the operation to perform.

You may assume that all queried employees appear in the employee list.

Output

For each query, output a list of employees according to the value of k:

• k = 1
  Print all colleagues of the queried employee — that is, all employees who share the same direct supervisor, excluding the employee themselves and excluding the top-level boss.

• k = 2
  Print the supervisors of the queried employee, starting from the nearest (direct boss) and moving upward through the hierarchy until reaching the top-level boss.

• k = 3
  Print all subordinates of the queried employee.
  First print all direct subordinates, followed by their subordinates, and so on recursively (from nearest to farthest).

Each employee is printed on its own line in the format:

firstname lastname

If no employees satisfy the query (e.g., no colleagues, no supervisors, or no subordinates), print nothing for that query.

Sample Input  Download

Sample Output  Download

Tags

Discuss