Submission #1162508

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162508		alexander707070	September (APIO24_september)	C++20	100 / 100	75 ms	6708 KiB

september

#include<bits/stdc++.h>
#define MAXN 100007
using namespace std;

const long long mod=1e9+9;

int n,m,bad,ans;
int parent[MAXN],deg[MAXN];
long long hesh[10],power[MAXN];
bool in[MAXN];

void reset_hesh(){
	for(int i=0;i<m;i++)hesh[i]=0;
}

int solve(int N, int M, vector<int> F,vector< vector<int> > S){
	n=N; m=M; ans=0;

	for(int i=0;i<n;i++){
		in[i]=false; deg[i]=0;
	}
	reset_hesh();

	for(int i=0;i<n;i++){
		parent[i]=F[i]; 
		if(parent[i]!=-1)deg[parent[i]]++;
	}

	power[0]=1;
	for(int i=1;i<n;i++)power[i]=(power[i-1]*2)%mod;

	for(int i=0;i<n-1;i++){
		for(int f=0;f<m;f++){
			
			if(f==0){
				deg[parent[S[f][i]]]--;
				if(in[parent[S[f][i]]])bad--;

				in[S[f][i]]=true;
				bad+=deg[S[f][i]];
			}
			
			hesh[f]+=power[S[f][i]];
		}
		
		for(int f=0;f<m;f++){
			if(f<m-1 and hesh[f]!=hesh[f+1])break;
			if(f==m-1 and bad==0){
				ans++; reset_hesh();
			}
		}
	}

	return ans;
}   

/*int main(){

	cout<<solve(3, 1, {-1, 0, 0}, {{1, 2}})<<"\n";
	cout<<solve(5, 2, {-1, 0, 0, 1, 1}, {{1, 2, 3, 4}, {4, 1, 2, 3}})<<"\n";

	return 0;
}*/

• 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