Submission #1158698

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158698		rayan_bd	September (APIO24_september)	C++20	45 / 100	221 ms	46508 KiB

september

#include <bits/stdc++.h>

using namespace std;


const int mxB = 28;
const int mxN = 1e5+1000;
const int mxK = 6;
vector<int> adj[mxN];
int st[mxN],en[mxN],nxt[mxN][mxK],idx[mxN][mxK],lt[mxN][mxK],dp[mxK][mxB][mxN],rmax[mxN][mxK],lg[mxN],timer=-1,K,prev_calc=1;

void dfs(int u=0,int par=-1){
	st[u]=++timer;
	for(int j=0;j<K;++j) lt[timer][j]=idx[u][j];
	for(auto it:adj[u]){
		if(it!=par){
			dfs(it,u);
		}
	}
	en[u]=timer;
}

void build_sparse(int N){
	for(int i=0;i<N;++i){
		for(int j=0;j<K;++j){
			dp[j][0][i]=lt[i][j];
		}
	}
	for(int k=0;k<K;++k){
		for(int i=1;i<mxB;++i){
    		for(int j=0;j+(1<<i)<=N;++j){
    			dp[k][i][j]=max(dp[k][i-1][j],dp[k][i-1][j+(1<<(i-1))]);
    		}
    	} 
    }
}

void calc_log(int N){
	while(prev_calc<=N){
		lg[prev_calc]=__lg(prev_calc);
		++prev_calc;
	}
}

int qry(int l,int r,int ck){
	int cnt=r-l+1;
	return max(dp[ck][lg[cnt]][l],dp[ck][lg[cnt]][r-(1<<lg[cnt])+1]);
}

void reset(int N){
	timer=-1;
	for(int i=0;i<=N+5;++i){
		adj[i].clear();
		for(int j=0;j<=K;++j){
			for(int k=0;k<mxB;++k){
				dp[j][k][i]=rmax[i][j]=lt[i][j]=nxt[i][j]=idx[i][j]=0ll;
			}
		}
	}
}

int solve(int N,int M,vector<int> F,vector<vector<int>> S){
	K=M;
	reset(N);

	for(int i=1;i<N;++i) adj[F[i]].push_back(i);

	for(int i=0;i<M;++i){
		for(int j=1;j<=S[i].size();++j){
			idx[S[i][j-1]][i]=j;
		}
	}

	dfs();
	build_sparse(N);
	calc_log(N);

	for(int i=0;i<M;++i){
		for(int j=0;j<N;++j){
			nxt[j][i]=qry(st[j],en[j],i);
		}
	}

	for(int i=0;i<M;++i){
		for(int j=1;j<=N-1;++j){
			rmax[j][i]=max(rmax[j-1][i],nxt[S[i][j-1]][i]);
		}
	}

	int mx_p=1,ans=1;
	vector<int> points(M,1);
	while(mx_p<N-1){
		int na=0;
		for(int j=0;j<M;++j){
			if(points[j]==rmax[points[j]][j]) ++na,++points[j];
			else points[j]=max(points[j],rmax[points[j]][j]);
			mx_p=max(mx_p,points[j]);
		}
		if(na==M) ++ans;
	}

	return ans;
}

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