Submission #1157477

#	Time	Username	Problem	Language	Result	Execution time	Memory
1157477		rayan_bd	September (APIO24_september)	C++20	59 / 100	166 ms	56256 KiB

september

#include <bits/stdc++.h>

using namespace std;


const int mxB = 17;
const int mxN = 1e5+10;
vector<int> adj[mxN];
int st[mxN],en[mxN],nxt[mxN][5],idx[mxN][5],lt[mxN][5],dp[5][mxB][mxN],rmax[mxN][5],timer=-1,K;

// next[u] -> index of the rightmost node that belongs to the u nodes subtree

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<5;++j){
			dp[j][0][i]=lt[i][j];
		}
	}
	for(int i=1;i<mxB;++i){
    	for(int j=0;j+(1<<i)<=N;++j){
    		for(int k=0;k<K;++k){
    			dp[k][i][j]=max(dp[k][i-1][j],dp[k][i-1][j+(1<<(i-1))]);
    		}
    	}
    }
}

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

void reset(int N){
	timer=-1;
	for(int i=0;i<=N;++i) adj[i].clear();
}

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

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

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

	dfs();
	build_sparse(N);

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

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

	int idx=1,ans=0,sz=S[0].size();

	while(idx<=sz){
		int mx=idx;
		for(int j=0;j<K;++j) mx=max(rmax[idx][j],mx);
		if(mx==idx) ++ans,++idx;
		else idx=mx;
	}

	return ans;
}

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