1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <string>
#include <vector>
#include <iostream>
#include <fstream>
#include <algorithm>

int main() {
	int k;
	int n0;
	std::vector<int> n_i;

	// 0. Get first k and n_0
	// ------------------------
	std::cin >> k;
	n_i.reserve(k);

	std::cin >> n0;
	n_i.push_back(n0);

	// pair: { dependantOn, propReqPpl }
	std::vector<std::vector<std::pair<int, long long>>> meetingsMatrix;

	// 1. Fill the matrix with first level meetings
	{
		std::vector<std::pair<int, long long>> initialK;
		initialK.reserve(n_i[0]);
		for (int i = 1; i <= n_i[0]; i++) {
			initialK.push_back({ i, 1 });
		}
		meetingsMatrix.push_back(initialK); // day 1
	}

	// 2. Fill the matrix with all the remaining meetings
	int tempN;
	int tempA;
	for (int i = 1; i < k; i++) {
		std::cin >> tempN;
		n_i.push_back(tempN);

		std::vector<std::pair<int, long long>> currentRow;
		currentRow.reserve(tempN);

		for (int j = 0; j < tempN; j++) {
			std::cin >> tempA;
			currentRow.push_back({ tempA, 1 });
		}
		meetingsMatrix.push_back(currentRow);
	}

	// 3. Backpropagate min required employee count from leaves to roots
	for (int i = k - 1; i > 0; i--) {
		std::vector<long long> childSum(n_i[i - 1], 0);

		for (int j = 0; j < n_i[i]; j++) {
			int parentIdx = meetingsMatrix[i][j].first;
			if (parentIdx > 0) {
				childSum[parentIdx - 1] += meetingsMatrix[i][j].second;
			}
		}

		for (int j = 0; j < n_i[i - 1]; j++) {
			if (childSum[j] > 0) {
				meetingsMatrix[i - 1][j].second = childSum[j];
			}
			else {
				meetingsMatrix[i - 1][j].second = 1;
			}
		}
	}

	// 4. Find maximum required employees over all days
	long long finalM = 0;

	for (int i = 0; i < k; i++) {
		long long daySum = 0;
		for (int j = 0; j < n_i[i]; j++) {
			daySum += meetingsMatrix[i][j].second;
		}
		if (daySum > finalM) finalM = daySum;
	}

	std::cout << finalM;
	return 0;
}