Connection Status:
Competition Arena > GoodCompanyDivTwo

GoodCompanyDivTwo

SRM 619 · 2013-12-22 · by hyy5159

SRM 619 · 2013-12-22 · by hyy5159 · Brute Force
Class Name: GoodCompanyDivTwo
Return Type: int
Method Name: countGood
Arg Types: (vector<int>, vector<int>)
Problem Statement

Problem Statement

Shiny has a company. There are N employees in her company. The employees are numbered 0 through N-1 in order in which they joined the company.


Employee 0 is the only employee with no boss. Every other employee has precisely one direct boss in the company. You are given a int[] superior with N elements. Element 0 of superior will be -1 to denote that employee 0 has no boss. For each i between 1 and N-1, inclusive, element i of superior will be the number of the boss of employee i.


For each employee, their boss joined the company before them. Formally, for each i between 1 and N-1, inclusive, superior[i] will be between 0 and i-1, inclusive.


Each employee only does one type of work. You are given a int[] workType with N elements. (Different integers represent different types of work.)


Each employee of the company has their own department. The department of employee x is formed by employee x and all the employees such that x is their boss. Formally, for any y different from x, employee y belongs into the department of employee x if and only if superior[y]=x. Note that if superior[z]=y and superior[y]=x, employee z does not belong into the department of employee x.


A department is called diverse if no two employees in the department do the same type of work. Compute and return the number of diverse departments in Shiny's company.

Constraints

  • superior will contain between 1 and 100 elements, inclusive.
  • workType will contain the same number of elements as superior.
  • Each element of workType will be between 1 and 100, inclusive.
  • superior[0] will be -1.
  • For each valid i>0, superior[i] will be between 0 and i-1, inclusive.
Examples
0)
{-1, 0}
{1, 2}
Returns: 2

The department of employee 0 contains employees 0 and 1. The department of employee 1 contains employee 1 only. Both departments are diverse.

1)
{-1, 0}
{1, 1}
Returns: 1

The departments are the same as in Example 0. However, now the department of employee 0 is not diverse: it contains two employees who do the same type of work. Only the department of employee 1 is now diverse.

2)
{-1, 0, 1, 1}
{1, 4, 3, 2}
Returns: 4

Note that in this test case the department of employee 0 contains only employees 0 and 1. Employees 2 and 3 do not belong into the department of employee 0.

3)
{-1, 0, 1, 0, 0}
{3, 3, 5, 2, 2}
Returns: 4
4)
{-1, 0, 1, 1, 1, 0, 2, 5}
{1, 1, 2, 3, 4, 5, 3, 3}
Returns: 7

Submissions are judged against all 100 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class GoodCompanyDivTwo with a public method int countGood(vector<int> superior, vector<int> workType) · 100 test cases · 2 s / 256 MB per case

Submitting as anonymous