Submission #991297

#	Time	Username	Problem	Language	Result	Execution time	Memory
991297		amirhoseinfar1385	September (APIO24_september)	C++17	100 / 100	331 ms	29284 KiB

september

#include "september.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10,maxm=6;
int n,m,lnk[maxm][maxn],all[maxm][maxn],te[maxn];
vector<int>adj[maxn];
void clear(){
	for(int i=0;i<m;i++){
		for(int j=0;j<=n;j++){
			lnk[i][j]=0;
			all[i][j]=0;
			te[j]=0;
		}
	}
	for(int j=0;j<=n;j++){
		adj[j].clear();
	}
}

int calt(int u=0,int ind=0){
	int ret=te[u];
	for(auto x:adj[u]){
		ret=max(ret,calt(x));
	}
	if(u!=0){
		lnk[ind][te[u]]=ret;
	}
	return ret;
}
int res=0;

void calc(){
	for(int j=0;j<m;j++){
		for(int i=0;i<n-1;i++){
			te[all[j][i]]=i;
		}
		calt(0,j);
	}
	map<int,int>mp;
	set<int>st;
	int maxa=0;
	for(int i=0;i<n-1;i++){
		for(int j=0;j<m;j++){
			maxa=max(maxa,lnk[j][i]);
			st.insert(all[j][i]);
			mp[all[j][i]]++;
			if(mp[all[j][i]]==m){
				st.erase(all[j][i]);
			}
		}
		//cout<<i<<" "<<maxa<<" "<<(int)st.size()<<endl;
		if(maxa<=i&&(int)st.size()==0){
			res++;
		}
	}
}



int solve(int N, int M, std::vector<int> F, std::vector<std::vector<int>> S) {
	n=N;
	m=M;
	res=0;
	for(int i=1;i<n;i++){
		adj[F[i]].push_back(i);
	}
	for(int i=0;i<m;i++){
		for(int j=0;j<n-1;j++){
			all[i][j]=S[i][j];
		}
	}
	calc();
	clear();
	return res;
}

• 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