#include "september.h"
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#define v vector
#define u_m unordered_map
#define u_s unordered_set
#define q queue
using namespace std;
// Transform vector F into child lookup
u_m<int, u_s<int>> children;
// This shall be the record keeper for volunteers
u_m<int, int> recordCount;
// This shall be for tracking which leaves fall on the same day
q<int> dayFall;
// This shall be for optimization - tracks if we've seen a certain leaf
v<bool> tracked;
void accountFor(int leaf) {
if (!(tracked[leaf])) {
dayFall.push(leaf);
tracked[leaf] = true;
for (auto iter = children[leaf].begin(); iter != children[leaf].end(); iter++) {
accountFor(*iter);
}
}
}
int solve(int N, int M, v<int> F, v<v<int>> S) {
children.clear(); recordCount.clear();
tracked.clear(); tracked.resize(N);
int days = 0;
for (int nodeInd = 1; nodeInd < N; nodeInd++) {
children[F[nodeInd]].insert(nodeInd);
}
// Traverse the records
for (int recordInd = 0; recordInd < N - 1; recordInd++) {
// Take in new leaves
for (int volunteerID = 0; volunteerID < M; volunteerID++) {
int leaf = S[volunteerID][recordInd];
accountFor(leaf);
recordCount[leaf]++;
}
// Check the same-day list if any leaf's records have been satisfied
if (!(dayFall.empty())) {
int front = dayFall.front();
while (recordCount[front] == M) {
dayFall.pop();
if (dayFall.empty()) break;
front = dayFall.front();
}
}
// The list being empty means everyone has been accepted for in that day
if (dayFall.empty()) days++;
}
return days;
}
