제출 #1157483

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1157483		rayan_bd	9월 (APIO24_september)	C++20	59 / 100	207 ms	94112 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<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))]);
    		}
    	}
    } 
}

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;
	int k=lg[cnt];
	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+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=S.size();
	reset(N);

	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);
	calc_log(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