Submission #1309304

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309304		zzzzzzzzzzzzzzz	September (APIO24_september)	C++20	100 / 100	148 ms	14776 KiB

september

/*#include <vector>

int solve(int N, int M, std::vector<int> F, std::vector<std::vector<int>> S);

#include "september.h"

#include <cassert>
#include <cstdio>
#include <vector>

void taskcase() {
	int N, M;
	assert(2 == scanf("%d%d", &N, &M));
	
	std::vector<int> F(N);
	F[0] = -1;
	for (int i = 1; i < N; ++i)
  		assert(1 == scanf("%d", &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)
  			assert(1 == scanf("%d", &S[i][j]));
  	
	printf("%d\n", solve(N, M, F, S));
}

int main() {
	int T;
	assert(1 == scanf("%d", &T));
	while(T--) taskcase();
	return 0;
}
*/

#include "september.h"

#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> g;
vector<int> child;
vector<int> parent;
vector<int> erased;
set<int> temp;

void dfs(int node){
	child[node]=g[node].size();
	for(int i:g[node]) dfs(i);
}

void erase1(int node){
	if(!erased[node]) return;
	//cout << node << " " <<  child[node] << "\n";
	if(child[node]==0){
		child[parent[node]]--;
		if(temp.find(node)!=temp.end()) temp.erase(node);
		erase1(parent[node]);
	} else{
		temp.insert(node);
	}
}

int solve(int N, int M, vector<int> F, vector<vector<int>> S) {
	temp.clear();erased.clear();g.clear();child.clear();
	erased.resize(N);g.resize(N);child.resize(N);
	parent=F;
	int ret=0;
	map<int,int> chk1;

	for(int i=1;i<N;i++) g[F[i]].push_back(i);
	dfs(0);
	for(int i=0;i<N-1;i++){
		for(int j=0;j<M;j++){
			chk1[S[j][i]]++;
			if(chk1[S[j][i]]==M) chk1.erase(S[j][i]);
		}
		erased[S[0][i]]=1;
		erase1(S[0][i]);
		//cout << i << " " << chk1.size() << " " << temp.size() << "\n";
		if(!chk1.empty() || !temp.empty()) continue;
		ret++;
	}
	return ret;
}

• Subtask 1: 11 / 11
• Subtask 2: 14 / 14
• Subtask 3: 5 / 5
• Subtask 4: 9 / 9
• Subtask 5: 5 / 5
• Subtask 6: 11 / 11
• Subtask 7: 9 / 9
• Subtask 8: 11 / 11
• Subtask 9: 9 / 9
• Subtask 10: 16 / 16