# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1202195 | ismoilmirzouz | September (APIO24_september) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (int i=a; i<b; i++)
int solve(int N, int M, std::vector<int> F, std::vector<std::vector<int>> S) {
// cout<<"f"<<endl;
int n = N, m = M;
vector<int> adj[n+1];
rep(i, 1, n) {
adj[F[i]].push_back(i+1);
}
vector<int> dp(n+1, -1);
rep(j,0,m){
rep(i,0,n-1){
dp[S[j][i]] = max(dp[S[j][i]], i);
}
}
function<void(int, int)> dfs = [&](int u, int p) {
for (auto v: adj[u]){
if (v == p) continue;
dfs(v, u);
dp[u] = max(dp[u], dp[v]);
}
};
dfs(1, 0);
int ans = 0;
int nxt = -1;
rep(i, 0, n-1){
// cout<<i<<" "<<nxt<<endl;
if (i > nxt){
ans++;
}
nxt = max(dp[S[0][i]],nxt);
}
return ans;
}
int main() {
int T;
cin>>T;
while(T--){
int N, M;
cin>>N>>M;
std::vector<int> F(N);
F[0] = -1;
for (int i = 1; i < N; ++i)
cin>>F[i];
std::vector<std::vector<int>> S(M, std::vector<int>(N - 1));
for (int i = 0; i < M; ++i)
for (int j = 0; j < N - 1; ++j)
cin>>S[i][j];
cout<<solve(N, M, F, S)<<endl;
}
return 0;
}