| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1160516 | jus_teng | September (APIO24_september) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// Build the tree as an adjacency list from the parent array
vector<vector<ll>> buildTree(ll numberOfNodes, vector<ll>& parent) {
vector<vector<ll>> adjacencyList(numberOfNodes);
for (ll i = 1; i < numberOfNodes; i++) {
adjacencyList[parent[i]].push_back(i);
}
return adjacencyList;
}
// Use DFS to find all leaf nodes
void findLeaves(ll node, vector<vector<ll>>& adjacencyList, vector<ll>& leaves) {
if (adjacencyList[node].empty() && node != 0) {
leaves.push_back(node);
}
for (ll child : adjacencyList[node]) {
findLeaves(child, adjacencyList, leaves);
}
}
// Solve for the maximum number of days
int solve(ll numberOfNodes, ll numberOfVolunteers, vector<ll> parent, vector<vector<ll>> volunteerRecords) {
// Build the tree
vector<vector<ll>> adjacencyList = buildTree(numberOfNodes, parent);
// Find all leaves
vector<ll> leaves;
findLeaves(0, adjacencyList, leaves);
sort(leaves.begin(), leaves.end());
// Special case: 0 or 1 leaf
if (leaves.size() <= 1) return leaves.size();
ll maxDays = 0;
// Try all permutations of leaf falling order
do {
// Initialize queues for each volunteer's record
vector<queue<ll>> sequences(numberOfVolunteers);
for (ll i = 0; i < numberOfVolunteers; i++) {
for (ll j = 0; j < volunteerRecords[i].size(); j++) {
sequences[i].push(volunteerRecords[i][j]);
}
}
ll currentDay = 1; // Start with day 1
bool isValid = true;
// Process each leaf in the current order
for (ll i = 0; i < leaves.size(); i++) {
bool found = false;
for (ll vol = 0; vol < numberOfVolunteers; vol++) {
if (!sequences[vol].empty() && sequences[vol].front() == leaves[i]) {
sequences[vol].pop();
found = true;
break;
}
}
if (!found) {
currentDay++; // New day if no volunteer expected this leaf
}
}
// Check if all records are fully used
for (ll vol = 0; vol < numberOfVolunteers; vol++) {
if (!sequences[vol].empty()) {
isValid = false;
break;
}
}
// Update maximum days if this order is valid
if (isValid) {
maxDays = max(maxDays, currentDay);
}
} while (next_permutation(leaves.begin(), leaves.end()));
return maxDays;
}
// Main function to handle multiple test cases
int main() {
ll testCases;
scanf("%lld", &testCases);
while (testCases--) {
ll numberOfNodes, numberOfVolunteers;
scanf("%lld %lld", &numberOfNodes, &numberOfVolunteers);
// Read the parent array
vector<ll> parent(numberOfNodes);
parent[0] = -1; // Root has no parent
for (ll i = 1; i < numberOfNodes; i++) {
scanf("%lld", &parent[i]);
}
// Read volunteers' records
vector<vector<ll>> volunteerRecords(numberOfVolunteers);
for (ll i = 0; i < numberOfVolunteers; i++) {
volunteerRecords[i].resize(numberOfNodes - 1); // Max possible leaves
for (ll j = 0; j < numberOfNodes - 1; j++) {
scanf("%lld", &volunteerRecords[i][j]);
}
}
// Get and print the result
ll result = solve(numberOfNodes, numberOfVolunteers, parent, volunteerRecords);
printf("%lld\n", result);
}
return 0;
}