| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1159695 | jus_teng | September (APIO24_september) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
/*
Topological BFS + Binary Search approach
Topological BFS adapted from https://cp-algorithms.com/graph/breadth-first-search.html and https://cp-algorithms.com/graph/topological-sort.html
Modifications:
- Topological DFS changed to topological BFS
- Queue and in-degree array instead of recursion
- Zero in-degree nodes processed first
Binary Search adapted from https://cp-algorithms.com/num_methods/binary_search.html
Modifications:
- Binary search is used for max possible K days instead of sorted array
- Each check does leaf removal through Topological BFS
*/
long long n, m;
vector<vector<long long>> adj;
vector<long long> inDegree;
bool topBFS(long long k, vector<vector<long long>>& s){
queue<long long> q;
vector<long long> remainingInDegree = inDegree;
for (long long i = 0; i < n; i++){
if (remainingInDegree[i] == 0){
q.push(i);
}
}
long long days = 0;
for (long long day = 0; day < k; day++){
if (q.empty()){
return false;
}
vector<long long> todayFallen;
while (!q.empty()){
long long node = q.front();
q.pop();
todayFallen.push_back(node);
for (long long parent : adj[node]){
remainingInDegree[parent]--;
if (remainingInDegree[parent] == 0){
q.push(parent);
}
}
}
set<long long> todaySet(todayFallen.begin(), todayFallen.end());
for (long long v = 0; v < m; v++){
long long start = (day == 0) ? 0 : (day * (n - 1) / k);
long long end = min((day + 1) * (n - 1) / k, (long long)s[v].size());
for (long long i = start; i < end; i++){
if (todaySet.find(s[v][i]) == todaySet.end()){
return false;
}
}
}
days++;
}
return days == k;
}
long long binSearch(vector<vector<long long>>& s){
long long left = 1, right = n - 1, ans = 1;
while (left <= right){
long long mid = (left + right) / 2;
if (topBFS(mid, s)){
ans = mid;
left = mid + 1;
}
else{
right = mid - 1;
}
}
return ans;
}
int main(){
long long t;
scanf("%lld", &t);
for (int i = 0; i < t; i++){
scanf("%lld %lld", &n, &m);
vector<long long> f(n);
vector<vector<long long>> s(m, vector<long long>(n - 1));
for (long long i = 1; i < n; i++){
scanf("%lld", &f[i]);
}
for (long long i = 0; i < m; i++){
for (long long j = 0; j < n - 1; j++){
scanf("%lld", &s[i][j]);
}
}
adj.assign(n, vector<long long>());
inDegree.assign(n, 0);
for (long long i = 1; i < n; i++){
long long parent = f[i];
adj[i].push_back(parent);
inDegree[parent]++;
}
printf("%lld\n", binSearch(s));
}
return 0;
}